QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782302 | #8892. Power Grid | DaiRuiChen007 | Compile Error | / | / | C++17 | 4.3kb | 2024-11-25 19:39:30 | 2024-11-25 19:39:31 |
Judging History
This is the latest submission verdict.
- [2024-11-25 19:39:31]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [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() { | ^~~~