QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#808815 | #8892. Power Grid | Max_s_xaM | 0 | 2ms | 12752kb | C++17 | 5.1kb | 2024-12-11 06:50:15 | 2024-12-11 06:50:16 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <numeric>
#include <iomanip>
#include <cassert>
typedef long long ll;
typedef double lf;
typedef unsigned long long ull;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 1000;
int n, m;
ll c[MAXN][MAXN], ans[MAXN][MAXN];
bool Tr;
inline void Swap()
{
Tr = 1;
int mx = max(n, m);
for (int i = 1; i <= mx; i++)
for (int j = 1; j < i; j++)
swap(c[i][j], c[j][i]);
swap(n, m);
}
inline void Print()
{
if (Tr)
{
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cout << ans[j][i] << ' ';
}
else
{
for (int i = 1; i <= n; i++, cout << '\n')
for (int j = 1; j <= m; j++)
cout << ans[i][j] << ' ';
}
}
ll a[MAXN], b[MAXN];
inline void Trans()
{
ll sum0 = 0, sum1 = 0;
for (int i = 2; i < n; i++) ans[i][1] = a[i], sum0 += a[i];
for (int i = 2; i < m; i++) ans[1][i] = b[i], sum1 += b[i];
ans[1][m] = a[1] - sum1;
ans[n][1] = b[1] - sum0;
ans[n][m] = b[m] - a[1] + sum1;
}
inline bool Solve()
{
int p = -1, q = -1, mx = 0, t;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (mx < c[i][j]) mx = c[i][j], p = i, q = j;
// for (int i = 1; i <= n; i++, cout << '\n')
// for (int j = 1; j <= m; j++)
// cout << c[i][j] << ' ';
// cout << p << ' ' << q << "\n";
t = (q == 1 ? 2 : q - 1);
for (int i = 1; i <= m; i++) b[i] = -c[p][i];
a[p] = 0;
for (int i = 1; i <= n; i++)
if (i != p)
{
if (c[i][q] + c[i][t] == b[t] - b[q]) a[i] = b[q] + c[i][q];
else if (c[i][q] > c[i][t]) a[i] = b[t] + c[i][t];
else a[i] = b[q] - c[i][q];
}
bool flag = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) flag &= abs(a[i] - b[j]) == c[i][j];
// for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << "\n";
// for (int i = 1; i <= m; i++) cout << b[i] << ' '; cout << "\n";
if (flag) return Trans(), 1;
t = (p == 1 ? 2 : p - 1);
for (int i = 1; i <= n; i++) a[i] = c[i][q];
b[q] = 0;
for (int i = 1; i <= m; i++)
if (i != q)
{
if (c[p][i] + c[t][i] == a[p] - a[t]) b[i] = a[p] - c[p][i];
else if (c[p][i] > c[t][i]) b[i] = a[t] - c[t][i];
else b[i] = a[p] + c[p][i];
}
flag = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) flag &= abs(a[i] - b[j]) == c[i][j];
if (flag) return Trans(), 1;
return 0;
}
int main()
{
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
Read(c[i][j]);
if (n == 1 || m == 1)
{
if (m == 1) Swap();
ll sum = 0;
for (int i = 1; i <= m; i++) sum += c[1][i];
sum /= m - 1;
for (int i = 1; i <= m; i++) ans[1][i] = sum - c[1][i];
Print();
return 0;
}
if (Solve()) Print();
else Swap(), Solve(), Print();
return 0;
}
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
Wrong Answer
Test #30:
score: 6
Accepted
time: 1ms
memory: 7708kb
input:
2 2 0 0 0 0
output:
0 0 0 0
result:
ok correct
Test #31:
score: 6
Accepted
time: 1ms
memory: 7776kb
input:
2 2 7 7 7 7
output:
0 0 -7 -7
result:
ok correct
Test #32:
score: 0
Wrong Answer
time: 1ms
memory: 7708kb
input:
2 4 7 7 7 7 7 7 7 7
output:
0 -7 -7 14 -7 0 0 -21
result:
wrong answer Rowsum 2 and columnsum 1 did not correspond to C
Subtask #5:
score: 0
Wrong Answer
Test #46:
score: 0
Wrong Answer
time: 0ms
memory: 7704kb
input:
2 4 253 431 207 483 243 65 289 13
output:
0 -431 -207 638 -253 0 0 -1121
result:
wrong answer Rowsum 2 and columnsum 1 did not correspond to C
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 2ms
memory: 12752kb
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:
wrong output format Unexpected end of file - int32 expected
Subtask #7:
score: 0
Wrong Answer
Test #68:
score: 15
Accepted
time: 0ms
memory: 7716kb
input:
2 2 5 52 52 5
output:
0 0 -5 -52
result:
ok correct
Test #69:
score: 0
Wrong Answer
time: 2ms
memory: 12712kb
input:
1000 1000 640 423 797 825 85 491 146 594 713 894 923 193 511 700 556 269 32 177 29 16 394 971 754 194 930 404 686 794 19 267 410 880 859 52 477 347 94 826 638 132 385 628 642 795 332 98 606 377 681 330 731 339 157 855 875 836 450 46 225 661 138 909 917 873 371 223 152 19 44 67 792 3 466 740 151 681 ...
output:
result:
wrong output format Unexpected end of file - int32 expected
Subtask #8:
score: 0
Skipped
Dependency #2:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%