QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#523518#8892. Power Gridskittles1412#0 0ms3860kbC++178.0kb2024-08-18 12:43:292024-08-18 12:43:29

Judging History

This is the latest submission verdict.

  • [2024-08-18 12:43:29]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 3860kb
  • [2024-08-18 12:43:29]
  • Submitted

answer

// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
vector<vector<T>> transposed(const vector<vector<T>>& arr) {
    int n = sz(arr), m = sz(arr[0]);

    vector ans(m, vector<T>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans[j][i] = arr[i][j];
        }
    }

    return ans;
}

template <typename T>
T checked_div(T a, T b) {
    assert(a % b == 0);
    return a / b;
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T>
int first_ne(const vector<T>& arr) {
    for (int i = 0; i < sz(arr); i++) {
        if (arr[i] != arr[0]) {
            return i;
        }
    }

    return -1;
}

template <typename T>
int first_row_ne(const vector<vector<T>>& arr) {
    return first_ne(arr);
}

template <typename T>
int first_col_ne(const vector<vector<T>>& arr) {
    return first_row_ne(transposed(arr));
}

int compute_sect(int x0, int a0, int x1, int a1) {
    bool bp = abs(x0 + a0 - x1) == a1, bm = abs(x0 - a0 - x1) == a1;
    if (bp ^ bm ^ true) {
        return -1;
    } else if (bp) {
        return x0 + a0;
    } else {
        return x0 - a0;
    }
}

int compute_sect_force(int x0, int a0, int x1, int a1) {
    int ans = compute_sect(x0, a0, x1, a1);
    assert(ans != -1);
    return ans;
}

void print(const vector<vector<int>>& ans) {
    dbg(ans);
    int m = sz(ans[0]);

    for (auto& a : ans) {
        for (int i = 0; i < m; i++) {
            cout << a[i] << " \n"[i == m - 1];
        }
    }
}

vector<vector<int>> solve_sums(vector<int> row_vals, vector<int> col_vals) {
    int n = sz(row_vals), m = sz(col_vals),
        sr = accumulate(begin(row_vals), end(row_vals), 0),
        sc = accumulate(begin(col_vals), end(col_vals), 0);

    int num = sr - sc, den = m - n;
    if (num % den) {
        return {};
    }
    int x = num / den;

    for (auto& a : row_vals) {
        a += x;
    }
    for (auto& a : col_vals) {
        a += x;
    }
    sr += n * x;
    sc += m * x;
    assert(sr == sc);

    vector ans(n, vector(m, int(0)));
    ans[0] = col_vals;
    for (int i = 0; i < n; i++) {
        ans[i][0] = row_vals[i];
    }

    ans[0][0] = row_vals[0] + col_vals[0] - sr;

    return ans;
}

optional<vector<int>> subset_sum(vector<int> arr, int targ, int mod) {
    int n = sz(arr);

    auto do_mod = [&](int x) -> int {
        if (0 <= x && x < mod) {
            return x;
        } else if (-mod <= x && x < 0) {
            return x + mod;
        }
        x %= mod;
        if (x < 0) {
            x += mod;
        }
        return x;
    };

    for (auto& a : arr) {
        a = do_mod(a);
    }
    targ = do_mod(targ);

    vector dp(n + 1, vector(mod, false));
    dp[n][targ] = true;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < mod; j++) {
            dp[i][j] = dp[i + 1][j] || dp[i + 1][do_mod(j + arr[i] - mod)];
        }
    }

    if (!dp[0][0]) {
        return {};
    }

    vector<int> ans;
    {
        int i = 0, j = 0;
        while (i < n) {
            int nj = do_mod(j + arr[i] - mod);
            if (dp[i + 1][nj]) {
                ans.push_back(i);
                j = nj;
            }
            i++;
        }
    }
    return ans;
}

optional<vector<int>> subset_sum(vector<int> arr, int targ) {
    return subset_sum(arr, targ,
                      *max_element(begin(arr), end(arr)) * sz(arr) + 10);
}

vector<vector<int>> solve_row_eq(const vector<vector<int>>& arr2) {
    assert(first_row_ne(arr2) == -1);

    int n = sz(arr2), m = sz(arr2[0]),
        arr_s = accumulate(begin(arr2[0]), end(arr2[0]), 0);

    optional<vector<int>> cinds;
    if (n == m) {
        cinds = subset_sum(arr2[0], checked_div(arr_s, 2));
    } else {
        auto carr = arr2[0];
        for (auto& a : carr) {
            a *= 2;
        }

        cinds = subset_sum(carr, arr_s, abs(n - m));
    }
    if (!cinds) {
        return {};
    }

    vector row_vals(n, 0), col_vals = arr2[0];
    for (auto& a : *cinds) {
        col_vals[a] = -col_vals[a];
    }

    return solve_sums(row_vals, col_vals);
}

vector<vector<int>> solve_same(const vector<vector<int>>& arr) {
    {
        auto ans = solve_row_eq(arr);
        if (sz(ans)) {
            return ans;
        }
    }

    return transposed(solve_row_eq(transposed(arr)));
}

vector<vector<int>> solve(vector<vector<int>> arr) {
    int n = sz(arr), m = sz(arr[0]);

    if (n == 1) {
        return solve_row_eq(arr);
    } else if (m == 1) {
        return transposed(solve_row_eq(transposed(arr)));
    }

    int r_id = first_row_ne(arr), c_id = first_col_ne(arr);
    if (r_id == -1 && c_id == -1) {
        return solve_same(arr);
    } else if (r_id == -1) {
        return solve_row_eq(arr);
    } else if (c_id == -1) {
        return transposed(solve_row_eq(transposed(arr)));
    } else if (r_id != 1) {
        swap(arr[1], arr[r_id]);
        auto ans = solve(arr);
        swap(ans[1], ans[r_id]);
        return ans;
    }

    array<int, 2> diffs {-1, -1};
    for (int i = 0; i < m; i++) {
        if (arr[0][i] != arr[1][i]) {
            int x = arr[0][i], y = arr[1][i];
            diffs = {x + y, abs(x - y)};
            break;
        }
    }

    assert(diffs[0] != -1);

    for (auto& r1 : diffs) {
        vector row_vals(n, int(0)), col_vals(m, int(0));

        row_vals[0] = 0;
        row_vals[1] = r1;

        for (int i = 0; i < m; i++) {
            col_vals[i] = compute_sect(0, arr[0][i], r1, arr[1][i]);
        }

        int c1 = first_ne(col_vals);
        if (c1 == -1) {
            continue;
        }

        for (int r = 2; r < n; r++) {
            row_vals[r] =
                compute_sect(col_vals[0], arr[r][0], col_vals[c1], arr[r][c1]);
        }

        bool bad = false;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (abs(row_vals[r] - col_vals[c]) != arr[r][c]) {
                    bad = true;
                }
            }
        }
        if (bad) {
            continue;
        }

        auto ans = solve_sums(row_vals, col_vals);
        if (sz(ans)) {
            return ans;
        }
    }

    assert(false);
}

void grade(const vector<vector<int>>& arr, const vector<vector<int>>& ans) {
    int n = sz(arr), m = sz(arr[0]);

    vector<int> row_sums(n), col_sums(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            row_sums[i] += ans[i][j];
            col_sums[j] += ans[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            assert(abs(row_sums[i] - col_sums[j]) == arr[i][j]);
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector arr(n, vector(m, int(0)));
    for (auto& a : arr) {
        for (auto& b : a) {
            cin >> b;
        }
    }

    auto ans = solve(arr);
    grade(arr, ans);
    print(ans);
}

int main() {
    init_io();
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

1 1
0

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Runtime Error

Test #23:

score: 0
Runtime Error

input:

1 1
0

output:


result:


Subtask #4:

score: 0
Runtime Error

Test #30:

score: 0
Runtime Error

input:

2 2
0 0
0 0

output:


result:


Subtask #5:

score: 0
Runtime Error

Test #46:

score: 15
Accepted
time: 0ms
memory: 3560kb

input:

2 4
253 431 207 483
243 65 289 13

output:

-243 -8 -232 44
57 0 0 0

result:

ok correct

Test #47:

score: 15
Accepted
time: 0ms
memory: 3616kb

input:

2 4
188 566 555 176
471 283 272 459

output:

-471 329 318 -413
46 0 0 0

result:

ok correct

Test #48:

score: 15
Accepted
time: 0ms
memory: 3860kb

input:

5 6
39 93 668 330 117 610
13 145 720 382 65 662
417 285 290 48 495 232
210 78 497 159 288 439
813 681 106 444 891 164

output:

488 181 -394 -56 391 -336
326 0 0 0 0 0
-104 0 0 0 0 0
103 0 0 0 0 0
-500 0 0 0 0 0

result:

ok correct

Test #49:

score: 15
Accepted
time: 0ms
memory: 3556kb

input:

4 7
330 140 57 520 147 685 359
70 540 457 120 547 285 41
168 638 555 22 645 187 139
425 45 38 615 52 780 454

output:

25 -389 -306 271 -396 436 110
151 0 0 0 0 0 0
249 0 0 0 0 0 0
-344 0 0 0 0 0 0

result:

ok correct

Test #50:

score: 0
Runtime Error

input:

10 10
853 399 803 868 626 195 356 314 232 136
409 45 359 424 182 249 88 130 212 308
134 320 84 149 93 524 363 405 487 583
60 394 10 75 167 598 437 479 561 657
50 404 0 65 177 608 447 489 571 667
828 374 778 843 601 170 331 289 207 111
457 3 407 472 230 201 40 82 164 260
34 420 16 49 193 624 463 505 ...

output:


result:


Subtask #6:

score: 0
Runtime Error

Test #58:

score: 0
Runtime Error

input:

1000 1000
1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 ...

output:


result:


Subtask #7:

score: 0
Runtime Error

Test #68:

score: 0
Runtime Error

input:

2 2
5 52
52 5

output:


result:


Subtask #8:

score: 0
Skipped

Dependency #2:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

0%