QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#523518 | #8892. Power Grid | skittles1412# | 0 | 0ms | 3860kb | C++17 | 8.0kb | 2024-08-18 12:43:29 | 2024-08-18 12:43:29 |
Judging History
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%