QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#597786#7857. (-1,1)-Sumplete000226TL 1ms7852kbC++174.6kb2024-09-28 18:48:132024-09-28 18:48:15

Judging History

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

  • [2024-09-28 18:48:15]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:7852kb
  • [2024-09-28 18:48:13]
  • 提交

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));
		for (int i = 1; i <= n * 2 + 2; i ++) vis[i] = 0;
		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: 1ms
memory: 7852kb

input:

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

output:

Yes
001
001
111

result:

ok n=3

Test #2:

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

score: -100
Time Limit Exceeded

input:

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

output:


result: