QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#597792#7857. (-1,1)-Sumplete000226TL 1343ms526748kbC++174.5kb2024-09-28 18:48:592024-09-28 18:49:00

Judging History

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

  • [2024-09-28 18:49:00]
  • 评测
  • 测评结果:TL
  • 用时:1343ms
  • 内存:526748kb
  • [2024-09-28 18:48:59]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=4e3+10,INF=INT_MAX>>1;

class Input {
	#define MX 1000000
	private :
		char buf[MX], *p1 = buf, *p2 = buf;
		inline char gc() {
			if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin);
			return p1 == p2 ? EOF : *(p1 ++);
		}
	public :
		Input() {
			#ifdef Open_File
				freopen("a.in", "r", stdin);
				freopen("a.out", "w", stdout);
			#endif
		}
		template <typename T>
		inline Input& operator >>(T &x) {
			x = 0; int f = 1; char a = gc();
			for(; ! isdigit(a); a = gc()) if(a == '-') f = -1;
			for(; isdigit(a); a = gc()) 
				x = x * 10 + a - '0';
			x *= f;
			return *this;
		}
		inline Input& operator >>(char &ch) {
			while(1) {
				ch = gc();
				if(ch != '\n' && ch != ' ') return *this;
			}
		}
		inline Input& operator >>(char *s) {
			int p = 0;
			while(1) {
				s[p] = gc();
				if(s[p] == '\n' || s[p] == ' ' || s[p] == EOF) break;
				p ++; 
			}
			s[p] = '\0';
			return *this;
		}
	#undef MX
} Fin;

class Output {
	#define MX 1000000
	private :
		char ouf[MX], *p1 = ouf, *p2 = ouf;
		char Of[105], *o1 = Of, *o2 = Of;
		void flush() { fwrite(ouf, 1, p2 - p1, stdout); p2 = p1; }
		inline void pc(char ch) {
			* (p2 ++) = ch;
			if(p2 == p1 + MX) flush();
		}
	public :
		template <typename T> 
		inline Output& operator << (T n) {
			if(n < 0) pc('-'), n = -n;
			if(n == 0) pc('0');
			while(n) *(o1 ++) = (n % 10) ^ 48, n /= 10;
			while(o1 != o2) pc(* (--o1));
			return *this; 
		}
		inline Output & operator << (char ch) {
			pc(ch); return *this; 
		}
		inline Output & operator <<(const char *ch) {
			const char *p = ch;
			while( *p != '\0' ) pc(* p ++);
			return * this;
		}
		~Output() { flush(); } 
	#undef MX
} Fout;

#define cin Fin
#define cout Fout
#define endl '\n'

int n;
bool a[maxn][maxn];
char s[maxn];
int R[maxn],C[maxn],sR[maxn],sC[maxn];
int S,T;

ll read() {
	ll x=0, f=1; char ch=' ';
	while(!isdigit(ch)) { ch=getchar(); if(ch=='-') f=-1; }
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-48), ch=getchar();
	return x*f;
}
struct Dinic{
	struct Edge{
		int to, cap, flow;
	};
	vector<Edge> edges;
	vector<int> G[maxn*2];
	bool vis[maxn*2];
	int m, s, t, d[maxn*2], cur[maxn*2];
	void charu(int from, int to, int cap) {
		edges.push_back({to, cap, 0});
		edges.push_back({from, 0, 0});
		int m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool bfs() {
		memset(vis, 0, sizeof(vis));
		
		queue<int> q;
		q.push(s), d[s]=0, vis[s]=1;
		while(!q.empty()) {
			int u=q.front(); q.pop();
			for(int id:G[u]) {
				Edge &e=edges[id];
				if(!vis[e.to]&&e.cap>e.flow) {
					q.push(e.to);
					vis[e.to]=1;
					d[e.to]=d[u]+1;
				}
			}
		}
		return vis[t];
	}
	int dfs(int u, int a) {
		if(u==t||a==0) return a;
		int flow=0, f;
		for(int &i=cur[u];i<G[u].size();i++) {
			Edge &e=edges[G[u][i]];
			if(d[u]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0) {
				e.flow+=f;
				edges[G[u][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(!a) break;
			}
		}
		return flow;
	}
	ll solve(int _s, int _t) {
		s=_s, t=_t; ll flow=0;
		while(bfs()) {
			memset(cur, 0, sizeof(cur));
			flow+=dfs(s, INF);
		}
		return flow;
	}
	void Build(){
		Rep(u,1,n) {
			for(int id:G[u]) {
				Edge e=edges[id];
				if(e.to!=s) {
					int v=e.to-n;
					if(e.cap==e.flow) a[u][v]^=1;
				}
			}
		}
	}
}tnt;

void solve(){
	cin>>n;
	Rep(i,1,n){
		cin>>s;
		for(int j=0;j<n;++j)a[i][j+1]=(s[j]=='+'),sR[i]+=a[i][j+1],sC[j+1]+=a[i][j+1];
	}
	Rep(i,1,n)cin>>R[i];
	Rep(i,1,n)cin>>C[i];
	Rep(i,1,n)if(sR[i]<R[i] || sC[i]<C[i])return cout<<"No\n",void();
	S=n+n+1,T=n+n+2;
	int sum=0,sam=0;
	static int seq[maxn];
	for (int i = 1; i <= n; i ++) seq[i] = i;
	random_shuffle(seq + 1, seq + 1 + n);
	Rep(x,1,n){
		int i = seq[x];
		tnt.charu(S,i,sR[i]-R[i]);
		tnt.charu(i+n,T,sC[i]-C[i]);
		sum+=sR[i]-R[i];
		sam+=sC[i]-C[i];
	}
	if(sum!=sam)return cout<<"No\n",void();
	Rep(i,1,n)Rep(j,1,n) tnt.charu(i,j+n,1);
	int res=tnt.solve(S,T);
	if(res!=sum)return cout<<"No\n",void();
	tnt.Build();
	cout<<"Yes\n";
	Rep(i,1,n){
		Rep(j,1,n)cout<<a[i][j];
		cout<<"\n";
	}
}

int main (){ return solve(),0; }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

input:

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

output:

Yes
10000000111100000100
01011001100110100001
01110011010100100110
01100111011110110111
11011101111101000100
10000001100001000001
11100100000100010101
00100010111001110111
00000100111000000101
11100010001111001001
00000011111100010111
10101000010011011001
00010111010011100000
01011101100001101011
01...

result:

ok n=20

Test #7:

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

input:

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

output:

Yes
1111010100111111010010011010001111100110011010101001010001110000101100101100100111110110100010010011
0110011010111101000110101010101010101001010010011100010010000010000010110110110010101101000100001111
0010001101111001000110000010010110000001000001001000011111111010011111001100101011100110110000...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 8ms
memory: 17504kb

input:

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

output:

Yes
01100110000110001010001111101000110001110111000000101101100011001000101001111010001011111101000101011001100011101101000110101100011011000100011000010100010000000000111001010001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 1225ms
memory: 524748kb

input:

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

output:

Yes
01101010100101111000101100000011000101110011100111111100010110111111100001000111011001100010110010000011101100101010111110101110010011011100010000101111100110010011100101100010110110101001000110011100010101110001001010010100011100011101011001110101110110001101111010110011101111101011011110100010...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 1235ms
memory: 526392kb

input:

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

output:

Yes
10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100011111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 1040ms
memory: 525416kb

input:

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

output:

Yes
01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 1220ms
memory: 526748kb

input:

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

output:

Yes
10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000011101101100100111000100000001111010110011010010000001111100010001101111011101111010001101111000011...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 1108ms
memory: 526704kb

input:

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

output:

Yes
01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 1343ms
memory: 525576kb

input:

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

output:

Yes
01100100000011010001101110111011101101111001111100000001011110100110101111001101110100000100100110000110000011011010100110010011001111000001000000010001011010110010101100100110101110000101110000011110000010111110111100011011011100100110101100111111110011111110101000101101011111011100001100000010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 954ms
memory: 526316kb

input:

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

output:

Yes
00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...

result:

ok n=4000

Test #16:

score: -100
Time Limit Exceeded

input:

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

output:


result: