QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#102937 | #5161. Last Guess | wangxuye | WA | 4ms | 11928kb | C++14 | 2.3kb | 2023-05-03 20:22:38 | 2023-05-03 20:22:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
const int inf=0x3f3f3f3f;
int head[N],edge[M],ver[M],nxt[M],d[N];
int n,m,maxflow=0,tot=1,s=N-1,t=N-2,ss=N-3,tt=N-4;
void add_edge(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
void add(int x,int y,int z)
{
if(z) add_edge(x,y,z),add_edge(y,x,0);
}
void add(int x,int y,int l,int r)
{
add(ss,y,l),add(x,tt,l),add(x,y,r-l);
}
queue<int> q;
bool bfs(int S,int T)
{
while(q.size()) q.pop();
memset(d,0,sizeof(d));
q.push(S),d[S]=1;
while(q.size())
{
int x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
{
int y=ver[i];
if(edge[i]&&!d[y]) d[y]=d[x]+1,q.push(y);
}
}
return d[T];
}
int dinic(int x,int flow,int t)
{
if(x==t||!flow) return flow;
int res=flow,k;
for(int i=head[x];i&&res;i=nxt[i])
{
int y=ver[i];
if(edge[i]&&d[y]==d[x]+1)
{
k=dinic(y,min(edge[i],res),t);
if(!k) d[y]=0;
res-=k,edge[i]-=k,edge[i^1]+=k;
}
}
return flow-res;
}
int g,l;
int minn[33],maxn[33],maxG[33];
int cnt[33],cntG[33];
bool black[33];
bool ban[33][510];
char st[N],col[N];
char ans[N];
int main()
{
scanf("%d%d",&g,&l);
for(int i=0;i<26;i++) minn[i]=0,maxn[i]=l;
memset(ban,false,sizeof(ban));
for(int i=1;i<g;i++)
{
for(int j=0;j<26;j++) cnt[j]=cntG[j]=black[j]=0;
scanf("%s%s",st+1,col+1);
for(int j=1;j<=l;j++)
{
if(col[j]=='G') ans[j]=st[j],cnt[st[j]-'a']++,cntG[st[j]-'a']++;
if(col[j]=='Y') cnt[st[j]-'a']++,ban[st[j]-'a'][j]=true;
if(col[j]=='B') black[st[j]-'a']=true,ban[st[j]-'a'][j]=true;
}
for(int j=0;j<26;j++)
{
maxG[j]=max(maxG[j],cntG[j]);
minn[j]=max(minn[j],cnt[j]);
if(black[j]) maxn[j]=min(maxn[j],cnt[j]);
}
}
add(s,ss,inf);
for(int i=0;i<26;i++)
add(s,i,minn[i]-maxG[i]),add(ss,i,maxn[i]-minn[i]);
for(int i=1;i<=l;i++)
{
if(ans[i]) continue;
add(26+i,t,1);
for(int ch=0;ch<26;ch++)
if(!ban[ch][i]) add(ch,26+i,1);
}
int flow=0;
while(bfs(s,t)) while(flow=dinic(s,inf,t)) maxflow+=flow;
for(int i=0;i<26;i++)
{
for(int j=head[i];j;j=nxt[j])
{
int y=ver[j];
if(26+1<=y&&y<=26+l&&!edge[j]) ans[y-26]=i+'a';
}
}
for(int i=1;i<=l;i++) putchar(ans[i]);
putchar('\n');
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8068kb
input:
4 5 reply YYGBB refer BBBGG puppy YYGBB
output:
upper
result:
ok
Test #2:
score: 0
Accepted
time: 3ms
memory: 7900kb
input:
2 12 aabbccddeeff GGGYGBYYYBBB
output:
aabzczzzbdde
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 10176kb
input:
25 500 qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqoqqqqqqqqqqqqqqqqqqqqqqoqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqjq...
output:
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzozzzzzzzz...
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 8076kb
input:
24 500 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzszzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
result:
ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
23 500 qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqq...
output:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
result:
ok
Test #6:
score: 0
Accepted
time: 4ms
memory: 9600kb
input:
22 500 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccoccccccccccccccccccccccccccccccccccccccccccccccccfccccccccccccccccccccccccccccccccc...
output:
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzxzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 11928kb
input:
30 20 azzzzzzzzzzzzzzzzzzz YBBBBBBBBBBBBBBBBBBB zazzzzzzzzzzzzzzzzzz BGBBBBBBBBBBBBBBBBBB zzazzzzzzzzzzzzzzzzz BBYBBBBBBBBBBBBBBBBB zzzazzzzzzzzzzzzzzzz BBBYBBBBBBBBBBBBBBBB zzzzazzzzzzzzzzzzzzz BBBBGBBBBBBBBBBBBBBB zzzzzazzzzzzzzzzzzzz BBBBBYBBBBBBBBBBBBBB zzzzzzazzzzzzzzzzzzz BBBBBBYBBBBBBBBBBBBB ...
output:
vajlabmpqyavasaaravu
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 9956kb
input:
31 20 azzzzzzzzzzzzzzzzzzz GBBBBBBBBBBBBBBBBBBB zazzzzzzzzzzzzzzzzzz BYBBBBBBBBBBBBBBBBBB zzazzzzzzzzzzzzzzzzz BBYBBBBBBBBBBBBBBBBB zzzazzzzzzzzzzzzzzzz BBBYBBBBBBBBBBBBBBBB zzzzazzzzzzzzzzzzzzz BBBBYBBBBBBBBBBBBBBB zzzzzazzzzzzzzzzzzzz BBBBBYBBBBBBBBBBBBBB zzzzzzazzzzzzzzzzzzz BBBBBBGBBBBBBBBBBBBB ...
output:
ayyduiasiaafbuqvayya
result:
ok
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 8028kb
input:
38 20 azzzzzzzzzzzzzzzzzzz YBBBBBBBBBBBBBBBBBBB zazzzzzzzzzzzzzzzzzz BGBBBBBBBBBBBBBBBBBB zzazzzzzzzzzzzzzzzzz BBYBBBBBBBBBBBBBBBBB zzzazzzzzzzzzzzzzzzz BBBGBBBBBBBBBBBBBBBB zzzzazzzzzzzzzzzzzzz BBBBGBBBBBBBBBBBBBBB zzzzzazzzzzzzzzzzzzz BBBBBYBBBBBBBBBBBBBB zzzzzzazzzzzzzzzzzzz BBBBBBYBBBBBBBBBBBBB ...
output:
oawaakoaaaeaoaasaaal
result:
FAIL Wrong answer: does not fit word 21