QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782302#8892. Power GridDaiRuiChen007Compile Error//C++174.3kb2024-11-25 19:39:302024-11-25 19:39:31

Judging History

This is the latest submission verdict.

  • [2024-11-25 19:39:31]
  • Judged
  • [2024-11-25 19:39:30]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1005,MAXV=2e6+5;
int n,m,u,v,a[MAXN][MAXN];
int x[MAXN],y[MAXN];
bitset <MAXV> f[MAXN];
bool solve() { //x_max > y_max
	int p=abs(n-m),z=0;
	for(int j=1;j<=m;++j) {
		y[j]=a[u][v]-a[u][j];
		z-=y[j];
	}
	vector <array<int,2>> ch;
	for(int i=1;i<=n;++i) {
		int lx=-a[i][v],rx=a[i][v];
		bool fl=true,fr=true;
		for(int j=1;j<=m;++j) {
			int px=y[j]+a[i][j],qx=y[j]-a[i][j];
			fl&=(px==lx||qx==lx);
			fr&=(px==rx||qx==rx);
		}
		if(!fl&&!fr) return false;
		else if(!fr) x[i]=lx;
		else if(!fl) x[i]=rx;
		else x[i]=lx,ch.push_back({i,rx-lx});
		z+=x[i];
	}
	int q=ch.size();
	f[0].reset(),f[0].set(0);
	for(int i=0;i<q;++i) {
		f[i+1]=f[i],f[i+1]<<=ch[i][1],f[i+1]|=f[i];
	}
	int S=-1;
	if(!p) S=-z;
	else {
		for(int r=(p-z%p)%p;r<MAXV;r+=p) if(f[q][r]) {
			S=r; break;
		}
	}
	if(S<0) return false;
	for(int i=q-1;~i;--i) if(!f[i][S]) {
		S-=ch[i][1],x[ch[i][0]]+=ch[i][1];
	}
	int sx=accumulate(x+1,x+n+1,0),sy=accumulate(y+1,y+m+1,0);
	if(!p) assert(sx==sy);
	else {
		assert((sx-sy)%p==0);
		int k=(sy-sx)/(n-m);
		for(int i=1;i<=n;++i) x[i]+=k;
		for(int j=1;j<=m;++j) y[j]+=k;
	}
	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;
	return true;
}
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m,u=v=1;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
		cin>>a[i][j];
		if(a[u][v]<a[i][j]) u=i,v=j;
	}
	if(solve()) {
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cout<<a[i][j]<<" \n"[j==m];
		return 0;
	}
	for(int i=1;i<=n;++i) for(int j=i+1;j<=m;++j) swap(a[i][j],a[j][i]);
	swap(n,m),swap(u,v);
	solve();
	for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) cout<<a[j][i]<<" \n"[j==n];
	return 0;
}#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 if(ins[v]) 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]);
//				cerr<<"ban("<<i<<","<<j<<") = "<<tx<<" "<<ty<<"\n";
				//ban (x,y)
			}
		}
	}
	for(int i=1;i<=tot;++i) if(!dfn[i]) tarjan(i);
//	for(int i=1;i<=tot;++i) {
//		cerr<<"u = "<<i<<": ";
//		for(int j:G[i]) cerr<<j<<" ";
//		cerr<<"\n";
//	}
//	for(int i=1;i<=tot;++i) cerr<<bel[i]<<" \n"[i==tot];
	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;
}

Details

answer.code:75:2: error: stray ‘#’ in program
   75 | }#include<bits/stdc++.h>
      |  ^
answer.code:75:3: error: ‘include’ does not name a type
   75 | }#include<bits/stdc++.h>
      |   ^~~~~~~
answer.code:78:11: error: redefinition of ‘const int MAXN’
   78 | const int MAXN=1005;
      |           ^~~~
answer.code:4:11: note: ‘const int MAXN’ previously defined here
    4 | const int MAXN=1005,MAXV=2e6+5;
      |           ^~~~
answer.code:79:5: error: redefinition of ‘int n’
   79 | int n,m,a[MAXN][MAXN],rid[MAXN][2],cid[MAXN][2];
      |     ^
answer.code:5:5: note: ‘int n’ previously declared here
    5 | int n,m,u,v,a[MAXN][MAXN];
      |     ^
answer.code:79:7: error: redefinition of ‘int m’
   79 | int n,m,a[MAXN][MAXN],rid[MAXN][2],cid[MAXN][2];
      |       ^
answer.code:5:7: note: ‘int m’ previously declared here
    5 | int n,m,u,v,a[MAXN][MAXN];
      |       ^
answer.code:79:9: error: redefinition of ‘int a [1005][1005]’
   79 | int n,m,a[MAXN][MAXN],rid[MAXN][2],cid[MAXN][2];
      |         ^
answer.code:5:13: note: ‘int a [1005][1005]’ previously declared here
    5 | int n,m,u,v,a[MAXN][MAXN];
      |             ^
answer.code:94:5: error: redefinition of ‘int x [1005]’
   94 | int x[MAXN],y[MAXN];
      |     ^
answer.code:6:5: note: ‘int x [1005]’ previously declared here
    6 | int x[MAXN],y[MAXN];
      |     ^
answer.code:94:13: error: redefinition of ‘int y [1005]’
   94 | int x[MAXN],y[MAXN];
      |             ^
answer.code:6:13: note: ‘int y [1005]’ previously declared here
    6 | int x[MAXN],y[MAXN];
      |             ^
answer.code:95:8: error: redefinition of ‘int main()’
   95 | signed main() {
      |        ^~~~
answer.code:59:8: note: ‘int main()’ previously defined here
   59 | signed main() {
      |        ^~~~