QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353278#7857. (-1,1)-Sumpleteucup-team3215AC ✓795ms669176kbC++203.7kb2024-03-14 00:38:342024-03-14 00:38:36

Judging History

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

  • [2024-03-14 00:38:36]
  • 评测
  • 测评结果:AC
  • 用时:795ms
  • 内存:669176kb
  • [2024-03-14 00:38:34]
  • 提交

answer

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

using namespace std;

constexpr int N = 4e3;

template<typename T = int>
struct /*Maksim1744*/ Dinic {
	struct Edge {
		int v, u;
		T f, c;
	};
	vector<Edge> ed;
	vector<vector<int> > e;
	int n, st, fin;
	T flow;

	vector<int> ptr, ds, que;

	Dinic(int n_, int st_, int fin_) : n(n_), st(st_), fin(fin_), flow(0) {
		e.resize(n);
		ptr.resize(n);
		ds.resize(n);
		que.resize(n);
	}

	void ae(int v, int u, T c, T bc = 0, T f = 0) {
		int w = int(ed.size());
		ed.push_back({v, u, f, c});
		ed.push_back({u, v, -f, bc});
		e[v].push_back(w);
		e[u].push_back(w + 1);
	}

	bool bfs(T scale) {
		fill(ds.begin(), ds.end(), -1);
		ds[st] = 0;
		int sz = 1;
		que[0] = st;
		for (int it = 0; it < sz; it++) {
			int v = que[it];
			for (int i : e[v])
				if (ed[i].f + scale <= ed[i].c && ds[ed[i].u] == -1) {
					ds[ed[i].u] = ds[v] + 1;
					if (ed[i].u == fin)
						return 1;
					que[sz++] = ed[i].u;
				}
		}
		return 0;
	}

	T dfs(int v, T w, T cs) {
		if (v == fin)
			return w;
		int &i = ptr[v];
		while (i >= 0) {
			auto &t = ed[e[v][i]];
			if (ds[t.u] == ds[v] + 1 && t.f + cs <= t.c) {
				T o = dfs(t.u, min(w, t.c - t.f), cs);
				if (o) {
					t.f += o;
					ed[e[v][i] ^ 1].f -= o;
					return o;
				}
			}
			i--;
		}
		return 0;
	}

	T get(int scale = 30) {
		for (T i = ((T(1)) << scale); i > 0; i >>= 1)
			while (bfs(i)) {
				for (int j = 0; j < n; j++)
					ptr[j] = int(e[j].size()) - 1;
				while (T w = dfs(st, numeric_limits<T>::max(), i))
					flow += w;
			}
		return flow;
	}
};

bool a[N][N], u[N][N], dr[N], dc[N];
int rt[N], ct[N], br[N][2], bc[N][2];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  Dinic<> mf(2 * n + 2, 2 * n, 2 * n + 1);
  for (int i = 0; i < n; ++i) if (string s; cin >> s)
  for (int j = 0; j < n; ++j) a[i][j] = s[j] == '+', br[i][1] += s[j] == '+', br[i][0] -= s[j] == '-', bc[j][1] += s[j] == '+', bc[j][0] -= s[j] == '-';
  for (int i = 0; i < n; ++i) cin >> rt[i];
  for (int i = 0; i < n; ++i) cin >> ct[i];
  vector<string> ans(n, string(n, '0'));
  auto mark = [&](int i, int j, bool w) {
    if (u[i][j]) return;
    u[i][j] = 1, ans[i][j] = '0' + (a[i][j] == w);
    br[i][1] -= a[i][j], br[i][0] += !a[i][j];
    bc[j][1] -= a[i][j], bc[j][0] += !a[i][j];
    if (a[i][j] == w) rt[i] -= 2 * a[i][j] - 1, ct[j] -= 2 * a[i][j] - 1;
  };
  for (int ch = 1; ch--; ) {
    for (int i = 0; i < n; ++i) if (!dr[i] && (rt[i] >= br[i][1] || rt[i] <= br[i][0])) if (dr[i] = ch = 1)
    for (int j = 0; j < n; ++j) mark(i, j, rt[i] >= br[i][1]);
    for (int i = 0; i < n; ++i) if (!dc[i] && (ct[i] >= bc[i][1] || ct[i] <= bc[i][0])) if (dc[i] = ch = 1)
    for (int j = 0; j < n; ++j) mark(j, i, ct[i] >= bc[i][1]);
  }
  for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j) {
    if (!dr[i] && !dc[j] && rt[i] > 0 && ct[j] > 0 && a[i][j]) mark(i, j, 1);
    else if (!dr[i] && !dc[j] && rt[i] < 0 && ct[j] < 0 && !a[i][j]) mark(i, j, 0);
    else if (u[i][j]) ;
    else if (a[i][j]) mf.ae(i, n + j, 1);
    else              mf.ae(n + j, i, 1);
  }
  int s[2]{};
  for (int i = 0; i < n; ++i) if (rt[i] > 0) mf.ae(2 * n, i, rt[i]), s[0] += rt[i]; else mf.ae(i, 2 * n + 1, -rt[i]), s[1] -= rt[i];
  for (int i = 0; i < n; ++i) if (ct[i] < 0) mf.ae(2 * n, n + i, -ct[i]), s[0] -= ct[i]; else mf.ae(n + i, 2 * n + 1, ct[i]), s[1] += ct[i];
  if (s[0] != s[1] || s[0] != mf.get(1)) return cout << "NO\n", 0;
  cout << "Yes\n";
  for (int i = 0; i < mf.ed.size(); i += 2) if (auto& e = mf.ed[i]; max(e.u, e.v) < 2 * n && e.f) {
    ans[min(e.u, e.v) % n][max(e.u, e.v) % n] = '1';
  }
  for (auto& s: ans) cout << s << '\n';
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

Yes
001
001
111

result:

ok n=3

Test #2:

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

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: 5876kb

input:

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

output:

NO

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

NO

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

input:

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

output:

Yes
01010000000000000000
00000000000010110000
10000100000000000000
10000011010000000000
00100000100101010001
10000000000000000000
01000000000100000000
00000010010001100001
00000000000000000110
10000000001100000001
00000001011100000101
00000000110001001100
00000000000011001001
00000000000001011000
00...

result:

ok n=20

Test #7:

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

input:

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

output:

Yes
1111010100111111010010011010100111110111000101010110000000000000000000000000000000000000000000000000
0110011010111101000110101010101010101001010010011100010010000010000010110110101000000000000000000000
0010001101100110111000000010010110000001000001001000011111110000000000000000000000000000000000...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 11ms
memory: 19556kb

input:

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

output:

Yes
11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 677ms
memory: 669176kb

input:

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

output:

Yes
00000000100001000000100000000010000001010010000100001000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 623ms
memory: 654728kb

input:

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

output:

Yes
01110110010110010100110001100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110101110011111111010110011110100101001110110011010110100010110110000100111101...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 638ms
memory: 656544kb

input:

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

output:

Yes
01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 675ms
memory: 652812kb

input:

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

output:

Yes
01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 679ms
memory: 653520kb

input:

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

output:

Yes
01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 789ms
memory: 661584kb

input:

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

output:

Yes
01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 795ms
memory: 662424kb

input:

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

output:

Yes
00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...

result:

ok n=4000

Test #16:

score: 0
Accepted
time: 533ms
memory: 51476kb

input:

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

output:

Yes
10011000000100110011110001111011011110010000011110010001111001000001111110000001000100000010101000001011100111010101110000011000101000101111101001011001101000001101010001110101001111001110010110101101001110011100000011011111100100110110111011010011000001000100110101110110100110110100110101010110...

result:

ok n=4000

Test #17:

score: 0
Accepted
time: 532ms
memory: 51388kb

input:

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

output:

Yes
10100010101111100110100011001001011101001011100010001011100000010010001011101111101000010110010001101000011010101010110100011101101110110110010101100101001100111111010110000110010110111100101010111000001100101001000110010100001010110100100101011011101110101100001110100001011001111110001000001010...

result:

ok n=3999

Test #18:

score: 0
Accepted
time: 554ms
memory: 51380kb

input:

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

output:

Yes
11111110011000110001110000010110001000110100111101110110000111000100001000101000001010101100001111110001001001011100100000110010101001101011001101110110011110100001100110010111010010100001011111011000100010110001100000001110011001011010111001111011000000010110101001010001000110100000100110000010...

result:

ok n=3998

Test #19:

score: 0
Accepted
time: 527ms
memory: 51152kb

input:

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

output:

NO

result:

ok n=4000

Test #20:

score: 0
Accepted
time: 554ms
memory: 51308kb

input:

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

output:

NO

result:

ok n=3999

Test #21:

score: 0
Accepted
time: 567ms
memory: 51504kb

input:

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

output:

NO

result:

ok n=3998

Test #22:

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

input:

2
+-
--
0 -1
-1 2

output:

NO

result:

ok n=2

Test #23:

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

input:

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

output:

NO

result:

ok n=20

Test #24:

score: 0
Accepted
time: 362ms
memory: 51252kb

input:

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

output:

NO

result:

ok n=4000

Test #25:

score: 0
Accepted
time: 275ms
memory: 51284kb

input:

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

output:

Yes
10011010110001001101110011011100110001110011001110010110011101100001110001110011001000001111001010111110011000110011001011010000100001100001111111111100010000000100110011011111001011111000011000001000101011000010011001101100010101010010011110111000001100010111001110110100001010010101011100111111...

result:

ok n=3999

Test #26:

score: 0
Accepted
time: 265ms
memory: 51400kb

input:

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

output:

Yes
00111000100010000001111001010111101011110101011101101011111010110000001001000010011110100111000000110000011000110000101000100001011000100010110101000101010100010100100100001001010011110000100000011010111001100010010101111000110101100111101000101111111000100110001011010011110111111110000110110100...

result:

ok n=4000

Test #27:

score: 0
Accepted
time: 261ms
memory: 51460kb

input:

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

output:

Yes
01100101001110110010001100100011001110001100110001101001100010011110001110001100110111110000110101000001100111001100110100101111011110011110000000000011101111111011001100100000110100000111100111110111010100111101100110010011101010101101100001000111110011101000110001001011110101101010100011000000...

result:

ok n=3999

Test #28:

score: 0
Accepted
time: 264ms
memory: 51472kb

input:

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

output:

Yes
11000111011101111110000110101000010100001010100010010100000101001111110110111101100001011000111111001111100111001111010111011110100111011101001010111010101011101011011011110110101100001111011111100101000110011101101010000111001010011000010111010000000111011001110100101100001000000001111001001011...

result:

ok n=4000

Extra Test:

score: 0
Extra Test Passed