QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#781535#8892. Power GridDaiRuiChen0070 2ms7740kbC++172.3kb2024-11-25 16:24:542024-11-25 16:25:00

Judging History

This is the latest submission verdict.

  • [2024-11-25 16:25:00]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 7740kb
  • [2024-11-25 16:24:54]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1005;
int n,m,a[MAXN][MAXN],rid[MAXN][2],cid[MAXN][2];
vector <int> G[MAXN*4];
int low[MAXN*4],dfn[MAXN*4],dcnt,stk[MAXN*4],tp,bel[MAXN*4],scnt;
bool ins[MAXN*4];
void tarjan(int u) {
	low[u]=dfn[u]=++dcnt,stk[++tp]=u,ins[u]=true;
	for(int v:G[u]) {
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) {
		++scnt;
		while(ins[u]) bel[stk[tp]]=scnt,ins[stk[tp--]]=false;
	}
}
int x[MAXN],y[MAXN];
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>a[i][j];
	int tot=0;
	for(int i=2;i<=n;++i) rid[i][0]=++tot;
	for(int i=2;i<=m;++i) cid[i][0]=++tot;
	for(int i=2;i<=n;++i) rid[i][1]=++tot;
	for(int i=2;i<=m;++i) cid[i][1]=++tot;
	for(int i=2;i<=n;++i) for(int j=2;j<=m;++j) {
		for(int tx:{1,-1}) for(int ty:{1,-1}) {
			if(abs(tx*a[i][1]+ty*a[1][j]-a[1][1])!=a[i][j]) {
				int u=(tx==1),v=(ty==1);
				G[rid[i][u]].push_back(cid[j][v^1]);
				G[cid[j][v]].push_back(rid[i][u^1]);
				//ban (x,y)
			}
		}
	}
	for(int i=1;i<=tot;++i) if(!dfn[i]) tarjan(i);
	for(int i=2;i<=n;++i) {
		assert(bel[rid[i][0]]!=bel[rid[i][1]]);
		if(bel[rid[i][0]]<bel[rid[i][1]]) a[i][1]*=-1;
	}
	for(int i=2;i<=m;++i) {
		assert(bel[cid[i][0]]!=bel[cid[i][1]]);
		if(bel[cid[i][0]]<bel[cid[i][1]]) a[1][i]*=-1;
	}
	for(int i=2;i<=n;++i) for(int j=2;j<=m;++j) {
		a[i][j]=a[i][1]+a[1][j]-a[1][1];
	}
//	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cerr<<a[i][j]<<" \n"[j==m];
	x[1]=0;
	for(int j=1;j<=m;++j) y[j]=x[1]-a[1][j];
	for(int i=2;i<=n;++i) x[i]=y[1]+a[i][1];
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) assert(a[i][j]==x[i]-y[j]);
	ll sx=0,sy=0;
	for(int i=1;i<=n;++i) sx+=x[i];
	for(int j=1;j<=m;++j) sy+=y[j];
	if(n==m) assert(sx==sy);
	else assert((sx-sy)%(n-m)==0);
	if(n!=m) {
		ll k=(sx-sy)/(m-n);
		for(int i=1;i<=n;++i) x[i]+=k;
		for(int j=1;j<=m;++j) y[j]+=k;
	}
	sx=0,sy=0;
	for(int i=1;i<=n;++i) sx+=x[i];
	for(int j=1;j<=m;++j) sy+=y[j];
	assert(sx==sy);
	memset(a,0,sizeof(a));
	for(int i=2;i<=n;++i) a[i][1]=x[i];
	for(int j=2;j<=m;++j) a[1][j]=y[j];
	a[1][1]=x[1]+y[1]-sx;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cout<<a[i][j]<<" \n"[j==m];
	return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

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

input:

1 1
0

output:

0

result:

ok correct

Test #2:

score: 8
Accepted
time: 1ms
memory: 7640kb

input:

1 1
0

output:

0

result:

ok correct

Test #3:

score: 8
Accepted
time: 2ms
memory: 7720kb

input:

1 2
1 1

output:

-1 1

result:

ok correct

Test #4:

score: 8
Accepted
time: 1ms
memory: 7736kb

input:

3 1
0
3
1

output:

2
-1
1

result:

ok correct

Test #5:

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

input:

2 2
1 1
1 1

output:

1 -1
-2 0

result:

ok correct

Test #6:

score: 0
Runtime Error

input:

3 3
2 1 1
2 1 1
0 1 3

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Runtime Error

Test #23:

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

input:

1 1
0

output:

0

result:

ok correct

Test #24:

score: 0
Runtime Error

input:

1 10
230 289 918 752 224 184 573 217 398 715

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #30:

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

input:

2 2
0 0
0 0

output:

0 0
0 0

result:

ok correct

Test #31:

score: 6
Accepted
time: 1ms
memory: 7724kb

input:

2 2
7 7
7 7

output:

7 -7
-14 0

result:

ok correct

Test #32:

score: 0
Wrong Answer
time: 1ms
memory: 7660kb

input:

2 4
7 7 7 7
7 7 7 7

output:

7 -14 0 0
-21 0 0 0

result:

wrong answer Rowsum 2 and columnsum 3 did not correspond to C

Subtask #5:

score: 0
Wrong Answer

Test #46:

score: 0
Wrong Answer
time: 1ms
memory: 7652kb

input:

2 4
253 431 207 483
243 65 289 13

output:

-243 -8 -232 44
-449 0 0 0

result:

wrong answer Rowsum 2 and columnsum 2 did not correspond to C

Subtask #6:

score: 0
Runtime Error

Test #58:

score: 0
Runtime Error

input:

1000 1000
1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 ...

output:


result:


Subtask #7:

score: 0
Runtime Error

Test #68:

score: 15
Accepted
time: 2ms
memory: 7656kb

input:

2 2
5 52
52 5

output:

52 -52
-57 0

result:

ok correct

Test #69:

score: 0
Runtime Error

input:

1000 1000
640 423 797 825 85 491 146 594 713 894 923 193 511 700 556 269 32 177 29 16 394 971 754 194 930 404 686 794 19 267 410 880 859 52 477 347 94 826 638 132 385 628 642 795 332 98 606 377 681 330 731 339 157 855 875 836 450 46 225 661 138 909 917 873 371 223 152 19 44 67 792 3 466 740 151 681 ...

output:


result:


Subtask #8:

score: 0
Skipped

Dependency #2:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

0%