QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353692#7857. (-1,1)-Sumpleteucup-team3215TL 780ms10032kbC++202.0kb2024-03-14 14:56:572024-03-14 14:56:58

Judging History

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

  • [2024-03-14 14:56:58]
  • 评测
  • 测评结果:TL
  • 用时:780ms
  • 内存:10032kb
  • [2024-03-14 14:56:57]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

constexpr int N = 4032;

bitset<N> edge[2][N], ans[N], used[2], neg[2];
int rt[N], ct[N], n;

int nx(int j, uint64_t* a, uint64_t* b) {
  j = -~j / 64;
  while (j < N / 64 && !(a[j] & b[j])) ++j;
  if (j < N / 64) return j * 64 + __builtin_ctzll(a[j] & b[j]);
  else return N;
}

int nx(int j, auto& a, auto& b) { return nx(j, (uint64_t*)&a, (uint64_t*)&b); }

template <bool col>
bool match(int i) {
  for (int j = -1; (j = nx(j, edge[col][i], neg[!col])) < N; ) {
    edge[col][i][j] = 0;
    edge[!col][j][i] = 1;
    if (col) {
      ans[j][i] = !ans[j][i];
      neg[0][j] = ++rt[j] < 0;
    } else {
      ans[i][j] = !ans[i][j];
      neg[1][j] = ++ct[j] < 0;
    }
    return 1;
  }
  used[col][i] = 0;
  for (int j = -1; (j = nx(j, edge[col][i], used[!col])) < N; ) {
    if (!match<!col>(j)) continue;
    edge[col][i][j] = 0;
    edge[!col][j][i] = 1;
    if (col) ans[j][i] = !ans[j][i];
    else ans[i][j] = !ans[i][j];
    return 1;
  }
  return 0;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < n; ++i) if (string s; cin >> s)
  for (int j = 0; j < n; ++j) edge[1][j][i] = !(edge[0][i][j] = s[j] == '+');
  for (int i = 0; i < n; ++i) cin >> rt[i];
  for (int i = 0; i < n; ++i) cin >> ct[i];
  for (int i = 0; i < n; ++i) ct[i] = -ct[i], neg[0][i] = rt[i] < 0, neg[1][i] = ct[i] < 0;
  for (int ch = 1; ch--; ) {
    used[0].set();
    used[1].set();
    for (int i = 0; i < n; ++i) while (rt[i] > 0 && used[0][i] && match<0>(i)) --rt[i], ch = 1;
    for (int j = 0; j < n; ++j) while (ct[j] > 0 && used[1][j] && match<1>(j)) --ct[j], ch = 1;
  }
  for (int i = 0; i < n; ++i) if (rt[i] || ct[i]) return cout << "No\n", 0;
  cout << "Yes\n";
  for (int i = 0; i < n; ++i, cout << '\n')
  for (int j = 0; j < n; ++j) cout.put('0' + ans[i][j]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

Yes
111
001
001

result:

ok n=3

Test #2:

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

input:

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

output:

Yes
110
100
000

result:

ok n=3

Test #3:

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

input:

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

output:

Yes
01000011010000101110
11011001010010110011
00011100010001001101
10101011010000000110
10101010100001010100
10010011000001100010
11000000000100000100
01010010000001000010
00000000000000000000
10110011001100000001
00000001011100000101
10000000100000001000
00000000000011000000
00000000000001011000
00...

result:

ok n=20

Test #7:

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

input:

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

output:

Yes
0111001011000000101101100001100111110111000101010110101110000000101100101100100111110110100010010011
0100001010111101001101110100010101101001010010011100010000000010000010110110101111110010111011101111
1001101001011001000110100010010110000001000001001000011111111010000110001100101001100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 6ms
memory: 4344kb

input:

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

output:

Yes
11111111111111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 158ms
memory: 9560kb

input:

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

output:

Yes
01101001100101111000101100000011000111110011100111111100010111000000010010101000000010000000001000010001000000101000001000100000010000001000010000000010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 216ms
memory: 9720kb

input:

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

output:

Yes
11100011000011001011001111100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110101110011111111010110011110100101001110110011010110100010110110000100111101...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 219ms
memory: 9948kb

input:

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

output:

Yes
10110111111111000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 177ms
memory: 9620kb

input:

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

output:

Yes
01001100111110000110010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 200ms
memory: 9872kb

input:

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

output:

Yes
10011110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010000000110100010010111110001001100011111100011000111011011110010110101110110111010101100001...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 780ms
memory: 9928kb

input:

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

output:

Yes
01100000110011010001001010101010000111001111000111010100100000010101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 765ms
memory: 10032kb

input:

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

output:

Yes
00011011010100001100111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...

result:

ok n=4000

Test #16:

score: -100
Time Limit Exceeded

input:

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

output:


result: