QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #101809 | #6380. LaLa and Divination Magic | zhouhuanyi | WA | 3ms | 7776kb | C++11 | 2.6kb | 2023-05-01 10:46:09 | 2023-05-01 10:46:09 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<bitset>
#include<vector>
#define N 2000
#define M 4000
#define K 8000000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int op,x,y;
};
reads tong[K+1];
int n,m,length,ans;
char c[N+1][N+1];
bool used[M+1],vst[N+1],F[N+1][N+1][2][2];
bitset<N+1>B[N+1];
bitset<N+1>S1;
bitset<N+1>S2;
bitset<N+1>S3;
bitset<N+1>S4;
bitset<N+1>B1[M+1];
bitset<N+1>B2[M+1];
vector<int>E[N+1];
void add(int x,int y)
{
E[x].push_back(y);
return;
}
void dfs(int rt,int x)
{
if (x<=m) B1[rt][x]=1;
else B2[rt][x-m]=1;
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
dfs(rt,E[x][i]);
return;
}
void dfs2(int x,bitset<N+1>st1,bitset<N+1>st2)
{
if (x==m+1)
{
ans++;
return;
}
if (!(B2[x]&st1).count()&&!(B1[x]&st2).count()) vst[x]=0,dfs2(x+1,st1|B1[x],st2|B2[x]);
if (!(B2[x+m]&st1).count()&&!(B1[x+m]&st2).count()) vst[x]=1,dfs2(x+1,st1|B1[x+m],st2|B2[x+m]);
if (ans>n) return;
return;
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
cin>>c[i][j];
if (c[i][j]=='1') B[i][j]=1;
}
for (int i=1;i<=n;++i)
{
S1.reset(),S2.reset();
for (int j=1;j<=m;++j)
{
if (c[j][i]=='1') S1|=B[j];
else S2|=B[j];
}
for (int j=1;j<=i-1;++j)
{
if (S1[j]) F[j][i][1][1]=1;
if (S2[j]) F[j][i][1][0]=1;
}
S1.set(),S2.set();
for (int j=1;j<=m;++j)
{
if (c[j][i]=='1') S1&=B[j];
else S2&=B[j];
}
for (int j=1;j<=i-1;++j)
{
if (!S1[j]) F[j][i][0][1]=1;
if (!S2[j]) F[j][i][0][0]=1;
}
}
for (int i=1;i<=m;++i)
for (int j=i+1;j<=m;++j)
{
if (!F[i][j][1][1]) add(i+m,j),add(j+m,i);
if (!F[i][j][0][1]) add(i,j),add(j+m,i+m);
if (!F[i][j][1][0]) add(i+m,j+m),add(j,i);
if (!F[i][j][0][0]) add(i,j+m),add(j,i+m);
}
for (int i=1;i<=(m<<1);++i)
{
for (int j=1;j<=(m<<1);++j) used[j]=0;
dfs(i,i);
}
dfs2(1,S3,S4);
if (ans>n)
{
puts("-1");
return 0;
}
for (int i=1;i<=m;++i)
for (int j=i+1;j<=m;++j)
{
if (!F[i][j][1][1]) tong[++length]=(reads){1,i,j};
if (!F[i][j][0][1]) tong[++length]=(reads){2,i,j};
if (!F[i][j][1][0]) tong[++length]=(reads){3,i,j};
if (!F[i][j][0][0]) tong[++length]=(reads){4,i,j};
}
printf("%d\n",length);
for (int i=1;i<=length;++i) printf("%d %d %d\n",tong[i].x-1,tong[i].y-1,tong[i].op);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7720kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #2:
score: 0
Accepted
time: 2ms
memory: 5668kb
input:
3 3 101 011 111
output:
5 0 1 4 0 2 3 0 2 4 1 2 3 1 2 4
result:
ok Kout = 5, Kans = 6
Test #3:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #4:
score: 0
Accepted
time: 2ms
memory: 5672kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #5:
score: 0
Accepted
time: 1ms
memory: 7724kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #6:
score: 0
Accepted
time: 2ms
memory: 5688kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #7:
score: 0
Accepted
time: 3ms
memory: 7768kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #8:
score: 0
Accepted
time: 2ms
memory: 5676kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 7520kb
input:
1 1 1
output:
-1
result:
wrong answer Jury has a solution while the participant doesn't, Kans = 1