Ý tưởng

Nhận xét 1: Với mỗi nút ta chỉ cần bấm dưới ~k~ lần vì nếu bấm một nút ~x \ge k~ lần thì ta có thể bấm ~x-k~ lần với công dụng tương tự.

Nhận xét 2: Giá trị ô ~(x, y)~ bằng ~v~ tương đương với ràng buộc ~(row_x + col_y) \bmod k = v~. Nếu ta biết được số lần bấm ở một trong hai nút thì ta có thể suy ra số lần cần bấm ở nút còn lại.

Như vậy, ta cần nhóm các nút lại sao cho khi biết số lần bấm của một nút bất kì trong nhóm, ta sẽ suy ra được số lần bấm của tất cả các nút còn lại trong nhóm đó.

Các nhóm ta cần tìm chính là các thành phần liên thông nếu ta dựng đồ thị sao cho mỗi nút bấm là một nút trên đồ thị, và giá trị mỗi ô ~(x, y)~ nhớ được là một cạnh nối ~row_x~ với ~col_y~.

Như vậy ta chỉ cần quan tâm đến các nhóm có nhiều hơn ~1~ nút bấm. Và ta có thể giải bài toán độc lập trên từng nhóm.

Vậy làm thế nào để tính kết quả cho từng nhóm? Ta có thể thử toàn bộ ~k~ giá trị từ ~0~ đến ~k-1~ của một nút bất kì trong trong nhóm và tính giá trị các nút còn lại. Tuy nhiên cách này không đủ nhanh.

Nhận xét 3: Với một phương án bất kì của một nhóm nào đó, ta có thể tăng số lần bấm ở các hàng lên ~1~ và giảm số lần bấm ở các cột đi ~1~ (theo modulo ~k~) để được một phương án mới.

Giả sử ta có một phương án của nhóm là ~row_1, row_2, \dots, row_r, col_1, col_2 \dots col_c~, tập hợp các phương án của nhóm là: $$\begin{cases} row_i(x) &=& (row_i + x) \bmod k &(1 \le i \le r) \\ col_j(x) &=& (col_j - x) \bmod k &(1 \le j \le c) \end{cases}$$ với mọi ~0 \le x < k~.

Gọi ~f(x) = row_1(x) + row_2(x) + \dots + row_r(x) + col_1(x) + col_2(x) + col_c(x)~. Ta cần tìm ~\min(f(x))~ với mọi ~0 \le x < k~.

Xét hàm ~f(x)~ theo chiều tăng của ~x~, ta thấy nó có hệ số góc là ~r - c~ (vì ta tăng ~1~ ở tất cả các hàng và giảm ~1~ ở tất cả các cột). Ngoài ra cần có thêm:

• ~r~ điểm làm hàm giảm đi ~k~ (khi ~row_i(x) = 0~, số lần bấm ở hàng ~i~ giảm từ ~k - 1~ về ~0~ thay vì tăng lên ~1~)
• ~c~ điểm làm hàm tăng thêm ~k~ (khi ~col_j(x) = k - 1~, số lần bấm ở cột ~j~ tăng từ ~0~ lên ~k - 1~ thay vì giảm đi ~1~)

Sắp xếp các điểm hàm thay đổi theo chiều tăng dần là ~x_1, x_2, \dots, x_{r+c}~. Khi đó ~f(x)~ là hàm bậc nhất trên các đoạn ~[0, x_1 - 1], [x_1, x_2 - 1], \dots, [x_{r + c - 1}, x_{r + c} - 1], [x_{r + c}, k - 1]~. Để tìm ~\min(f(x))~, ta chỉ cần thử ~x~ ở tất cả các điểm đầu và cuối mỗi đoạn.

Code mẫu

Để tiện cho việc cài đặt, code bên dưới đánh số ~row_i~ là ~i-1~ (~1 \le i \le r~) và ~col_j~ là ~r + j - 1~ (~1 \le j \le c~).

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

int r, c, q, k, ans[N];
vector<array<int, 2>> adj[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c >> q >> k;
    for (int i = 0; i < q; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        --x;
        y = y - 1 + r;
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }
    fill(ans, ans + r + c, -1);
    for (int i = 0; i < r + c; ++i) {
        if (ans[i] > -1)
            continue;

        queue<int> qu;
        vector<int> comp;
        ans[i] = 0;
        qu.push(i);
        comp.push_back(i);
        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();
            for (auto e : adj[u]) {
                int v = e[0], val = (e[1] - ans[u] + k) % k;
                if (ans[v] == -1) {
                    ans[v] = val;
                    qu.push(v);
                    comp.push_back(v);
                } else if (ans[v] != val) {
                    cout << "-1\n";
                    return 0;
                }
            }
        }
        int slope = 0;
        long long sum = 0;
        vector<array<int, 2>> changingPoints;
        for (int u : comp) {
            sum += ans[u];
            if (u < r) {
                slope++;
                changingPoints.push_back({k - ans[u], -k});
            } else {
                slope--;
                changingPoints.push_back({ans[u] + 1, k});
            }
        }
        changingPoints.push_back({0, 0});
        changingPoints.push_back({k, 0});
        sort(changingPoints.begin(), changingPoints.end());
        int bestPos = 0;
        long long bestSum = sum;
        for (int i = 1; i < (int) changingPoints.size(); ++i) {
            if (changingPoints[i - 1][0] < changingPoints[i][0]) {
                if (sum + 1ll * slope * changingPoints[i - 1][0] < bestSum) {
                    bestSum = sum + 1ll * slope * changingPoints[i - 1][0];
                    bestPos = changingPoints[i - 1][0];
                }
                if (sum + 1ll * slope * (changingPoints[i][0] - 1) < bestSum) {
                    bestSum = sum + 1ll * slope * (changingPoints[i][0] - 1);
                    bestPos = changingPoints[i][0] - 1;
                }
            }
            sum += changingPoints[i][1];
        }
        for (int u : comp) {
            if (u < r) {
                ans[u] = (ans[u] + bestPos) % k;
            } else {
                ans[u] = (ans[u] - bestPos + k) % k;
            }
        }
    }
    cout << accumulate(ans, ans + r + c, 0ll) << '\n';
    for (int i = 0; i < r + c; ++i) {
        cout << ans[i] << " \n"[i == r - 1 || i == r + c - 1];
    }
    return 0;
}