QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #103938 | #6380. LaLa and Divination Magic | chenshi# | WA | 3ms | 11132kb | C++ | 2.0kb | 2023-05-07 22:13:12 | 2023-05-07 22:13:16 |
Judging History
answer
#include<cstdio>
#include<bitset>
using namespace std;
const int o=2010,O=o*o*2;
int n,m,cnt[o],I[O],J[O],typ[O],K,ch[O][2],tot,h[o],Cnt,st[o][o],tp[o],v[o],t;char s[o][o];bool flg;bitset<o> b[o][2];
struct Edge{int v,p;}e[O*2];
inline void ad(int U,int V){e[++Cnt].v=V;e[Cnt].p=h[U];h[U]=Cnt;}
bool Dfs(int nw,int val){
if(v[nw]) return v[nw]==val;
v[st[t][++tp[t]]=nw]=val;
for(int i=h[nw],j;i;i=e[i].p){
j=e[i].v;
if(nw==I[j]&&val-1-((typ[j]-1)&1)) if(!Dfs(J[j],((typ[j]-1)>>1)+1)) return false;
if(nw==J[j]&&((typ[j]-1)>>1)+1) if(!Dfs(I[j],val-1-((typ[j]-1)&1))) return false;
}
return true;
}
void dfs(int nw,int u){
if(flg) return;
if(nw>1&&!u){flg=1;printf("-1");return;}
if(nw>m) return;
if(cnt[nw]==n){dfs(nw+1,ch[u][1]);return;}
if(cnt[nw]==0){dfs(nw+1,ch[u][0]);return;}
if(!v[nw]){
t=nw;
if(Dfs(nw,1)) dfs(nw+1,ch[u][0]);
for(;tp[nw];v[st[nw][tp[nw]--]]=0);
if(Dfs(nw,2)) dfs(nw+1,ch[u][1]);
for(;tp[nw];v[st[nw][tp[nw]--]]=0);
}
else dfs(nw+1,ch[u][v[nw]-1]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cnt[j]+=(s[i][j]=='1');
for(int i=1;i<=m;++i)
if(cnt[i]==n) I[++K]=i,J[K]=i,typ[K]=4;
else if(!cnt[i]) I[++K]=i,J[K]=i,typ[K]=1;
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) b[j][s[i][j]-'0'].set(i);
for(int i=1;i<=m;++i) for(int j=i+1;j<=m;++j) if(cnt[i]&&cnt[i]<n&&cnt[j]&&cnt[j]<n){
if(!(b[i][1]&b[j][1]).count()) I[++K]=i,J[K]=j,typ[K]=1,ad(i,K),ad(j,K);
if(!(b[i][0]&b[j][1]).count()) I[++K]=i,J[K]=j,typ[K]=2,ad(i,K),ad(j,K);
if(!(b[i][1]&b[j][0]).count()) I[++K]=i,J[K]=j,typ[K]=3,ad(i,K),ad(j,K);
if(!(b[i][0]&b[j][0]).count()) I[++K]=i,J[K]=j,typ[K]=4,ad(i,K),ad(j,K);
}
for(int i=1;i<=n;++i) for(int u=0,j=1;j<=m;u=ch[u][s[i][j++]-48])
if(!ch[u][s[i][j]-48]) ch[u][s[i][j]-48]=++tot;
dfs(1,0);
if(flg) return 0;
printf("%d\n",K);
for(int i=1;i<=K;++i) printf("%d %d %d\n",I[i]-1,J[i]-1,typ[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7068kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #2:
score: 0
Accepted
time: 0ms
memory: 11132kb
input:
3 3 101 011 111
output:
2 2 2 4 0 1 4
result:
ok Kout = 2, Kans = 6
Test #3:
score: 0
Accepted
time: 2ms
memory: 5120kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #4:
score: 0
Accepted
time: 1ms
memory: 7036kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #5:
score: 0
Accepted
time: 2ms
memory: 5068kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #6:
score: 0
Accepted
time: 1ms
memory: 7168kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #7:
score: 0
Accepted
time: 2ms
memory: 5080kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #8:
score: 0
Accepted
time: 2ms
memory: 5068kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #9:
score: 0
Accepted
time: 1ms
memory: 9164kb
input:
1 1 1
output:
1 0 0 4
result:
ok Kout = 1, Kans = 1
Test #10:
score: 0
Accepted
time: 0ms
memory: 7116kb
input:
1 1 0
output:
1 0 0 1
result:
ok Kout = 1, Kans = 1
Test #11:
score: 0
Accepted
time: 2ms
memory: 4996kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #12:
score: 0
Accepted
time: 2ms
memory: 5012kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #13:
score: 0
Accepted
time: 2ms
memory: 5100kb
input:
2 4 0111 0010
output:
4 0 0 1 2 2 4 1 3 2 1 3 3
result:
ok Kout = 4, Kans = 15
Test #14:
score: 0
Accepted
time: 2ms
memory: 5128kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #15:
score: 0
Accepted
time: 0ms
memory: 7140kb
input:
4 2 10 11 01 00
output:
0
result:
ok Kout = 0, Kans = 0
Test #16:
score: 0
Accepted
time: 2ms
memory: 5076kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #17:
score: 0
Accepted
time: 3ms
memory: 9228kb
input:
2 4 0010 1000
output:
4 1 1 1 3 3 1 0 2 1 0 2 4
result:
ok Kout = 4, Kans = 15
Test #18:
score: 0
Accepted
time: 3ms
memory: 9120kb
input:
2 5 11101 00000
output:
13 3 3 1 0 1 2 0 1 3 0 2 2 0 2 3 0 4 2 0 4 3 1 2 2 1 2 3 1 4 2 1 4 3 2 4 2 2 4 3
result:
ok Kout = 13, Kans = 21
Test #19:
score: -100
Wrong Answer
time: 3ms
memory: 9236kb
input:
5 4 0010 1001 0011 0101 1011
output:
5 0 1 1 0 3 3 1 2 1 1 3 3 2 3 4
result:
wrong answer The output contains more solutions than intended.