QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#808815#8892. Power GridMax_s_xaM0 2ms12752kbC++175.1kb2024-12-11 06:50:152024-12-11 06:50:16

Judging History

This is the latest submission verdict.

  • [2024-12-11 06:50:16]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 12752kb
  • [2024-12-11 06:50:15]
  • Submitted

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;
}

詳細信息

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%