QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665322#7857. (-1,1)-SumpleteNCl3AC ✓1948ms147440kbC++202.9kb2024-10-22 11:21:522024-10-22 11:21:53

Judging History

你现在查看的是最新测评结果

  • [2024-10-22 11:21:53]
  • 评测
  • 测评结果:AC
  • 用时:1948ms
  • 内存:147440kb
  • [2024-10-22 11:21:52]
  • 提交

answer

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
constexpr int N = 4010;
constexpr int inf = 1e9 + 10;
constexpr ll llinf = 1e18 + 10;
constexpr int mod = 1e9 + 7;
void debug() {
    std::cerr << "\n";
}
template<typename T, typename... Args>
void debug(T val, const Args&... args) {
    std::cerr << val << " ";
    debug(args...);
}
template<typename T>
void debug(const std::vector<T>& vec) {
    for (const T& x : vec) std::cerr << x << ' ';std::cerr << "\n";
}
std::string s[N];
int r[N], c[N];
int mp[N][N], ans[N][N];
void ncl3() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
        for (int j = 0; j < n; j++) {
            mp[i][j] = (s[i][j] == '+' ? 1 : -1);
        }
    }
    for (int i = 0; i < n; i++) {
        std::cin >> r[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> c[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mp[i][j] == -1) {
                mp[i][j] = 1;
                r[i] += mp[i][j];
                c[j] += mp[i][j];
                ans[i][j] = 1;
            }
        }
    }
    std::set<std::pair<int, int>, std::greater<>> S;
    int cr = 0, cc = 0;
    for (int i = 0; i < n; i++) {
        // debug(r[i], c[i]);
        if (r[i] < 0 || r[i] > n || c[i] > n || c[i] < 0) {
            std::cout << "NO" << "\n";
            return;
        }
        cr += r[i]; cc += c[i];
        S.emplace(c[i], i);
    }
    if (cr != cc) {
        std::cout << "NO" << "\n";
    }
    std::vector<int> st(n);
    for (int i = 0; i < n; i++) {
        while (r[i]) {
            auto [cnt, j] = *S.begin();
            S.erase(S.begin());
            // debug(i, r[i], cnt, j);
            if (c[j]) {
                ans[i][j] ^= 1;
                r[i]--;c[j]--;
                st[j] = 1;
            }
            else {
                std::cout << "NO" << "\n";
                return;
            }
        }
        for (int j = 0; j < n; j++) {
            if (st[j] == 1) {
                st[j] = 0;
                S.emplace(c[j], j);
            }
        }
    }
    std::cout << "YES" << "\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << ans[i][j];
        }
        std::cout << "\n";
    }
}
/*
    预处理、找性质缩小范围、集合思想、正难则反、穷举
*/
int main() {
#ifdef LOCAL
    clock_t time = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        ncl3();
    }
#ifdef LOCAL
    std::cout << "Time Used:" << clock() - time << "ms" << "\n";
#endif
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6008kb

input:

3
+-+
-++
+-+
1 1 1
1 -1 3

output:

YES
111
111
111

result:

ok n=3

Test #2:

score: 0
Accepted
time: 0ms
memory: 7908kb

input:

3
---
-++
+++
-2 -1 0
-2 -1 0

output:

YES
110
100
000

result:

ok n=3

Test #3:

score: 0
Accepted
time: 1ms
memory: 7788kb

input:

3
+-+
-++
++-
1 0 2
2 2 -1

output:

NO

result:

ok n=3

Test #4:

score: 0
Accepted
time: 1ms
memory: 5800kb

input:

1
-
-1
1

output:

NO

result:

ok n=1

Test #5:

score: 0
Accepted
time: 1ms
memory: 5732kb

input:

1
-
0
0

output:

YES
0

result:

ok n=1

Test #6:

score: 0
Accepted
time: 1ms
memory: 5852kb

input:

20
+-------+-----+++-++
-+-++++----++-++-++-
-+++--+---+--+-++---
-+++-+--+----++---+-
+++-+-++++++-+-+---+
-++-----+----++++++-
+-++--+++++-++-+----
+-+----+---+-+++--+-
+++++-+++++----+--+-
------++++---+--++--
++++--------++++--+-
-+-+-++++-+-++-++--+
---+-++---+-++-++---
+-++++-++----+-+++--
+-+...

output:

YES
01100011111000111110
10101101010110110010
10000011010001001101
10000111011001110111
01101100000101010001
10010101100101101011
01010000000111100101
10111110111001110010
00000110111000100101
00000000001110111000
00001111111101110001
10100111101010100110
00011001111011011000
10111101101110100000
01...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 2ms
memory: 9892kb

input:

100
++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++
-++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++
--+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...

output:

YES
1110010000111010000001100110001111110111001101011111101100000000101100101100111111100010100010011010
0111011110111001000111000110000010101001011010011100010000000010000010110110110111100110111011100111
0011001001100010111001101010111110000000001001000001011101111110011010001100110011110110011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 12ms
memory: 20964kb

input:

500
--+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...

output:

YES
11000101000110101011000011011101010111110101100000010100010011001001001011001001101011001111001101110010111011111010001101000000000000011001011100010010011100100010001110110101011111011100001100000010001111101011100100011010010011111100010111100110011000000100001100111011000101101101100011101000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 1231ms
memory: 147440kb

input:

4000
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:

YES
00010101011111000010100011111010100011011110001100011011110111110010101110011000100111001001000011010101101000101111011111001011010000000101000000101011101111001011110111100010110110001001110111111001011101000001100110101100110100101101001011110110110110011111010010010000111111101111001000101011...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 1053ms
memory: 147048kb

input:

4000
+---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...

output:

YES
00110011010110001110111001100110100010110011000010111011010101000110100011010100010010111110101111111111100011010101011001000111010111010010100101110011101110100111001000010101000101100001101110000000101001010001100110000111010001011101100110110100100111001110110011110011101000100111010111001111...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 1590ms
memory: 146972kb

input:

4000
-+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...

output:

YES
10111100000101101010001100000111001111100110001111110110101101111110110001011110110101010110010101111101101001100001001100110101010111010100000101001100101111000100001100000101010011001011100101100000101101100000101110100111000001100001011111110111001000010011001001101100001110010101010110101001...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 1155ms
memory: 147076kb

input:

4000
+-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...

output:

YES
01110110000111011000001000111111110100001011111011000001010101000011101001100011101010100001000111101010111010000011110100001110111100111000010111110101000001101000101011000101110001000101111001000111010011101011101100011011100101000000101101110111011100111101101011100111001000001100111101110111...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 1488ms
memory: 146904kb

input:

4000
-+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...

output:

YES
10001100011101010111111010100100101000010100100011110000000110000111000000111010001111010101001111110010011001101110110111111011000010100000001010011100101110100001110111110110000111011000101010000111110001111011000010011000100010101100111101110001010111010000000000111001010101000100100111010011...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 669ms
memory: 147080kb

input:

4000
+--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...

output:

YES
01100000110011010001001010101011001111110001111100100011011110100110101101000111110100000100100110000100000011011111100110000010101101000001000000000101111010111010100100100110101110000101111000001010000010110010111100010010011101110110100100101111110011011010101100100001111111011100001000010010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 1948ms
memory: 146992kb

input:

4000
---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...

output:

YES
00011010010100001101111000000000001110011110110110011100100101010111011010001101100110010000001011001111100100101111011101100000111100101100001000010010001100111100010101101111111100001000100001001000010011001111110111011001001100000000001101101101111110011011111001110101111011110010001100010110...

result:

ok n=4000

Test #16:

score: 0
Accepted
time: 1526ms
memory: 146988kb

input:

4000
++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...

output:

YES
10011000000100110011110001111011011110010000011110010001111001000001111110000001000100000010101000001011100111010101110000011000101000101111101001011001101000001101010001110101001111001110010110101101001110011100000011011111100100110110111011010011000001000100110101110110100110110100110101010110...

result:

ok n=4000

Test #17:

score: 0
Accepted
time: 1594ms
memory: 146956kb

input:

3999
-+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...

output:

YES
10100010101111100110100011001001011101001011100010001011100000010010001011101111101000010110010001101000011010101010110100011101101110110110010101100101001100111111010110000110010110111100101010111000001100101001000110010100001010110100100101011011101110101100001110100001011001111110001000001010...

result:

ok n=3999

Test #18:

score: 0
Accepted
time: 1542ms
memory: 146920kb

input:

3998
--------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...

output:

YES
11111110011000110001110000010110001000110100111101110110000111000100001000101000001010101100001111110001001001011100100000110010101001101011001101110110011110100001100110010111010010100001011111011000100010110001100000001110011001011010111001111011000000010110101001010001000110100000100110000010...

result:

ok n=3998

Test #19:

score: 0
Accepted
time: 1139ms
memory: 146940kb

input:

4000
++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...

output:

NO

result:

ok n=4000

Test #20:

score: 0
Accepted
time: 1167ms
memory: 146972kb

input:

3999
-+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...

output:

NO

result:

ok n=3999

Test #21:

score: 0
Accepted
time: 1133ms
memory: 147228kb

input:

3998
--------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...

output:

NO

result:

ok n=3998

Test #22:

score: 0
Accepted
time: 0ms
memory: 5736kb

input:

2
+-
--
0 -1
-1 2

output:

NO

result:

ok n=2

Test #23:

score: 0
Accepted
time: 0ms
memory: 5852kb

input:

20
--+--------+---++-++
--+++-+----+--++-+++
-+-+-++++---+-+---++
+++-++--++-++-++--++
+---+----+-+++-++++-
----+++++--++----+-+
+-++++----++--++----
++++++-+-+-++-++--+-
-+--+-++++-+-+-+-+-+
--++-+-+--++-++--++-
+---+++-+++-+-+-++-+
+++-+--+++-++-+++-+-
--++--+-++-+--+-+-++
----++-+--+-+-++++-+
--+...

output:

NO

result:

ok n=20

Test #24:

score: 0
Accepted
time: 85ms
memory: 146552kb

input:

4000
++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...

output:

NO

result:

ok n=4000

Test #25:

score: 0
Accepted
time: 504ms
memory: 146624kb

input:

3999
-++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...

output:

YES
10011010110001001101110011011100110001110011001110010110011101100001110001110011001000001111001010111110011000110011001011010000100001100001111111111100010000000100110011011111001011111000011000001000101011000010011001101100010101010010011110111000001100010111001110110100001010010101011100111111...

result:

ok n=3999

Test #26:

score: 0
Accepted
time: 523ms
memory: 146736kb

input:

4000
++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...

output:

YES
00111000100010000001111001010111101011110101011101101011111010110000001001000010011110100111000000110000011000110000101000100001011000100010110101000101010100010100100100001001010011110000100000011010111001100010010101111000110101100111101000101111111000100110001011010011110111111110000110110100...

result:

ok n=4000

Test #27:

score: 0
Accepted
time: 1547ms
memory: 147244kb

input:

3999
-++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...

output:

YES
01100101001110110010001100100011001110001100110001101001100010011110001110001100110111110000110101000001100111001100110100101111011110011110000000000011101111111011001100100000110100000111100111110111010100111101100110010011101010101101100001000111110011101000110001001011110101101010100011000000...

result:

ok n=3999

Test #28:

score: 0
Accepted
time: 1520ms
memory: 147132kb

input:

4000
++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...

output:

YES
11000111011101111110000110101000010100001010100010010100000101001111110110111101100001011000111111001111100111001111010111011110100111011101001010111010101011101011011011110110101100001111011111100101000110011101101010000111001010011000010111010000000111011001110100101100001000000001111001001011...

result:

ok n=4000

Extra Test:

score: 0
Extra Test Passed