QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #478503 | #8490. Guess the String | rania__# | AC ✓ | 9ms | 3812kb | C++14 | 9.7kb | 2024-07-15 03:12:05 | 2024-07-15 03:12:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int query(int i,string s)
{
cout<<"? "<<i+1<<" "<<s<<endl;
int x;
cin>>x;
return x;
}
int main()
{
int n;
while(cin>>n)
{
if(n == 0)return 0;
string ans="";
for(int i=0;i<n;i++)
{
ans+='x';
}
for(int i=0;i+2<n;i++)
{
int q1=query(i,"aa");
//aa
if(q1 == 2)
{
ans[i]='a';
ans[i+1]='a';
i++;
continue;
}
if(q1 == 0)
{
//bb
//xba
int q2=query(i,"bb");
if(q2 == 0)
{
ans[i]='c';
ans[i+1]='c';
i++;
continue;
}
if(q2 == 1)
{
int q3=query(i+1,"ba");
if(q3 == 0)
{
ans[i]='b';
ans[i+1]='c';
int q4=query(i+1,"zb");
if(q4 == 1)
{
ans[i+2]='b';
}
else ans[i+2]='c';
i+=2;
continue;
}
if(q3 == 1)
{
///xba
///xbc
int q4=query(i+1,"bc");
if(q4 == 0)
{
ans[i]='b';
ans[i+1]='c';
ans[i+2]='a';
i+=2;
continue;
}
if(q4 == 1)
{
ans[i]='c';
ans[i+1]='b';
ans[i+2]='b';
i+=2;
continue;
}
if(q4 == 2)
{
ans[i]='c';
ans[i+1]='b';
ans[i+2]='c';
i+=2;
continue;
}
}
if(q3 == 2)
{
ans[i]='c';
ans[i+1]='b';
ans[i+2]='a';
i+=2;
continue;
}
}
if(q2 == 2)
{
ans[i]='b';
ans[i+1]='b';
i++;
continue;
}
}
if(q1 == 1)
{
int q2=query(i,"ba");
if(q2 == 2)
{
ans[i]='b';
ans[i+1]='a';
i++;
continue;
}
if(q2 == 1)
{
ans[i]='c';
ans[i+1]='a';
i++;
continue;
}
if(q2 == 0)
{
ans[i]='a';
int q3=query(i+1,"ba");
if(q3 == 2)
{
ans[i+1]='b';
ans[i+2]='a';
i+=2;
continue;
}
if(q3==0)
{
ans[i+1]='c';
int q4=query(i+1,"zb");
if(q4 == 1)
{
ans[i+2]='b';
}
if(q4 == 0)
{
ans[i+2]='c';
}
i+=2;
continue;
}
if(q3 == 1)
{
int q4=query(i+1,"bb");
if(q4 == 2)
{
ans[i+1]='b';
ans[i+2]='b';
}
if(q4 == 1)
{
ans[i+1]='b';
ans[i+2]='c';
}
if(q4 == 0)
{
ans[i+1]='c';
ans[i+2]='a';
}
i+=2;
continue;
}
}
}
}
int c=0;
for(int i=0;i<n;i++)
{
c+=ans[i]=='x';
}
if(c == 0)
{
}
else if(c == 1)
{
int q=query(n-2,"za");
if(q == 1)
{
ans[n-1]='a';
}
else
{
int q2=query(n-2,"zb");
if(q2 == 1)ans[n-1]='b';
else ans[n-1]='c';
}
}
else if(c == 2)
{
int q1=query(n-2,"aa");
if(q1 == 2)
{
ans[n-2]='a';
ans[n-1]='a';
}
else if(q1 == 0)
{
int q2=query(n-2,"bb");
if(q2 == 0)
{
ans[n-2]='c';
ans[n-1]='c';
}
else if(q2 == 1)
{
int q3=query(n-2,"bc");
if(q3 == 2)
{
ans[n-1]='c';
ans[n-2]='b';
}
else
{
ans[n-1]='b';
ans[n-2]='c';
}
}
else
{
ans[n-1]='b';
ans[n-2]='b';
}
}
else
{
/*
ans=1
ab
ans=0, second is c, first can be b or c
bz
ans=1, first is b
ans=0, first is c
ans=2
string is ab
ans = 1
first is a, second is c
*/
int q2=query(n-2,"ab");
if(q2 == 0)
{
ans[n-1]='a';
int q3=query(n-2,"bz");
if(q3 == 0)
{
ans[n-2]='c';
}
else ans[n-2]='b';
}
else if(q2 == 2)
{
ans[n-2]='a';
ans[n-1]='b';
}
else
{
ans[n-2]='a';
ans[n-1]='c';
}
}
/*
2 in 3 queries
bb
bc
cb
cc
aa
ans=2
string is aa
ans=0
bb
ans = 0
string is cc
ans = 1
bc
ans = 2
string is bc
else
string is cb
ans=2
string is bb
ans=1
ab
ans=0, second is c, first can be b or c
bz
ans=1, first is b
ans=0, first is c
ans=2
string is ab
ans = 1
first is a, second is c
*/
}
cout<<"! "<<ans<<endl;
}
}
/* if the answer is 2-> i know the first 2 are bb
if the answer is 1-> i know either the first or the second is an a
query ba
if answer is 2, i know the first and second are a, so im done
if answer is 1, i know the second index is a, and the first index is c so im done
if answer is 0, i know that the first index is c, second is either b or c
query 2.ba
if the answer is 2, im done
if the answer is 0, second index is c, third index is either b or c
query 2.bz, 1 means its a b, 0 means c
if the answer is 1, either first index is b or second is a
/*
c b a
c b
c
query 2.bb
if the answer is 2 im done
if the answer is 1 , second index is b, third index is c
if the answer is 0, second index is c, third is a
each 3 places solved in 4 queries
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
3 1 0 1 1 0
output:
? 1 aa ? 1 ba ? 2 ba ? 2 bb ! abc
result:
ok max queries count: 4
Test #2:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
2 2 2 1 2 2 1 0 1 2 0 1 0 2 0 2 2 1 0 0 2 0 1 2 2 1 1 2 0 0 0
output:
? 1 aa ! aa ? 1 aa ? 1 ab ! ab ? 1 aa ? 1 ab ? 1 bz ! ba ? 1 aa ? 1 bb ? 1 bc ! cb ? 1 aa ? 1 bb ! bb ? 1 aa ? 1 ab ? 1 bz ! ca ? 1 aa ? 1 bb ? 1 bc ! bc ? 1 aa ? 1 ab ! ac ? 1 aa ? 1 bb ! cc
result:
ok max queries count: 3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 1 0 0 1 3 1 0 2 3 1 2 1 3 0 1 2 3 0 1 0 0 3 0 0 0 0 3 1 1 0 1 3 1 2 0 0 3 0 1 1 1 3 0 1 0 1 3 1 0 0 0 3 0 0 0 1 3 1 0 1 1 3 0 1 1 2 3 0 0 1 3 2 1 3 0 1 1 0 3 1 1 0 0 3 1 2 0 1 3 0 2 0 1 3 2 0 1 3 1 1 1 3 0 2 0 0 3 1 0 1 0 3 0 2 1 3 2 0 0 3 1 0 1 2 0
output:
? 1 aa ? 1 ba ? 2 ba ? 2 zb ! acb ? 1 aa ? 1 ba ? 2 ba ! aba ? 1 aa ? 1 ba ? 2 za ! baa ? 1 aa ? 1 bb ? 2 ba ! cba ? 1 aa ? 1 bb ? 2 ba ? 2 zb ! bcc ? 1 aa ? 1 bb ? 2 za ? 2 zb ! ccc ? 1 aa ? 1 ba ? 2 za ? 2 zb ! cab ? 1 aa ? 1 ba ? 2 za ? 2 zb ! bac ? 1 aa ? 1 bb ? 2 ba ? 2 bc ! cbb ? 1 aa ? 1 bb ?...
result:
ok max queries count: 4
Test #4:
score: 0
Accepted
time: 4ms
memory: 3812kb
input:
4 1 0 0 1 1 4 1 2 0 1 2 4 1 2 2 4 1 0 1 1 0 0 4 0 1 2 0 0 4 0 0 1 0 0 4 1 2 0 0 4 0 2 1 1 4 0 0 0 0 4 0 1 0 1 1 4 1 0 2 0 0 4 2 1 2 4 0 1 1 0 0 0 4 0 1 1 2 1 4 1 0 1 1 0 1 4 1 1 0 0 4 0 1 1 0 1 4 0 1 0 1 0 1 4 0 1 1 1 0 1 4 0 1 0 0 0 1 4 2 1 0 1 4 0 1 1 2 0 0 4 1 0 1 0 0 1 4 0 1 1 0 0 1 4 1 2 1 2 4 ...
output:
? 1 aa ? 1 ba ? 2 ba ? 2 zb ? 3 za ! acba ? 1 aa ? 1 ba ? 3 aa ? 3 bb ? 3 bc ! babc ? 1 aa ? 1 ba ? 3 aa ! baaa ? 1 aa ? 1 ba ? 2 ba ? 2 bb ? 3 za ? 3 zb ! abcc ? 1 aa ? 1 bb ? 2 ba ? 3 za ? 3 zb ! cbac ? 1 aa ? 1 bb ? 3 aa ? 3 ab ? 3 bz ! ccca ? 1 aa ? 1 ba ? 3 aa ? 3 bb ! bacc ? 1 aa ? 1 bb ? 3 aa...
result:
ok max queries count: 6
Test #5:
score: 0
Accepted
time: 6ms
memory: 3580kb
input:
100 0 2 1 1 1 0 1 0 1 1 2 2 0 0 0 1 1 0 1 0 0 0 0 1 2 0 1 0 1 1 1 1 0 1 2 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 0 1 2 1 1 2 0 1 0 0 0 1 0 0 2 0 2 1 2 1 0 1 0 1 0 1 2 1 0 0 0 0 1 2 1 0 2 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 100 0 2 1 1 0 1 1 2 0 1 1 0 0 2 1 0 2 0 0 0 1 1 1 1 1 0 1 2 2 1 ...
output:
? 1 aa ? 1 bb ? 3 aa ? 3 ba ? 5 aa ? 5 ba ? 6 ba ? 6 bb ? 8 aa ? 8 ba ? 10 aa ? 12 aa ? 14 aa ? 14 bb ? 16 aa ? 16 bb ? 17 ba ? 17 bc ? 19 aa ? 19 ba ? 20 ba ? 20 zb ? 22 aa ? 22 bb ? 23 ba ? 25 aa ? 25 bb ? 26 ba ? 26 zb ? 28 aa ? 28 ba ? 30 aa ? 30 ba ? 31 ba ? 31 bb ? 33 aa ? 33 bb ? 34 ba ? 34 b...
result:
ok max queries count: 119
Test #6:
score: 0
Accepted
time: 3ms
memory: 3596kb
input:
4 0 2 1 0 0 4 1 0 1 0 0 0 4 2 2 4 1 0 0 0 0 1 4 1 1 1 1 4 0 0 1 0 1 4 0 1 0 1 0 0 4 2 0 2 4 0 1 1 0 1 4 0 0 0 0 4 1 0 1 0 1 4 0 1 1 2 1 4 1 0 1 1 0 0 4 1 2 1 0 0 4 2 0 1 2 4 0 1 1 2 0 0 4 2 0 2 4 1 2 1 1 4 2 0 2 4 1 0 0 0 0 0 4 1 2 1 2 4 1 0 1 1 0 0 4 0 1 1 1 0 0 4 0 1 1 2 0 1 4 1 0 0 0 0 0 4 0 2 1 ...
output:
? 1 aa ? 1 bb ? 3 aa ? 3 ab ? 3 bz ! bbca ? 1 aa ? 1 ba ? 2 ba ? 2 bb ? 3 za ? 3 zb ! acac ? 1 aa ? 3 aa ! aaaa ? 1 aa ? 1 ba ? 2 ba ? 2 zb ? 3 za ? 3 zb ! accb ? 1 aa ? 1 ba ? 3 aa ? 3 ab ! caac ? 1 aa ? 1 bb ? 3 aa ? 3 ab ? 3 bz ! ccba ? 1 aa ? 1 bb ? 2 ba ? 2 zb ? 3 za ? 3 zb ! bcbc ? 1 aa ? 3 aa...
result:
ok max queries count: 6
Test #7:
score: 0
Accepted
time: 4ms
memory: 3584kb
input:
5 0 2 1 1 1 5 1 1 1 1 1 5 2 1 0 0 0 5 0 1 1 0 1 1 5 0 0 1 2 0 1 5 0 1 1 2 2 5 0 2 0 1 1 0 5 1 0 0 0 0 0 5 1 0 1 0 1 1 5 0 1 1 0 1 2 5 0 0 1 2 0 0 5 2 1 0 1 1 5 0 1 1 2 1 0 0 5 1 0 1 2 1 0 1 5 1 0 1 0 1 2 5 1 2 0 0 0 0 5 1 2 1 0 2 5 0 1 0 0 0 1 0 5 0 1 0 0 0 1 2 5 1 2 0 0 0 0 5 0 2 1 1 0 0 5 0 1 0 1 ...
output:
? 1 aa ? 1 bb ? 3 aa ? 3 ba ? 4 za ! bbcaa ? 1 aa ? 1 ba ? 3 aa ? 3 ba ? 4 za ! cacaa ? 1 aa ? 3 aa ? 3 ba ? 4 ba ? 4 zb ! aaacc ? 1 aa ? 1 bb ? 2 ba ? 2 bc ? 4 aa ? 4 ab ! bcaac ? 1 aa ? 1 bb ? 3 aa ? 3 ba ? 4 za ? 4 zb ! ccbab ? 1 aa ? 1 bb ? 2 ba ? 2 bc ? 4 aa ! cbcaa ? 1 aa ? 1 bb ? 3 aa ? 3 bb ...
result:
ok max queries count: 7
Test #8:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
20 0 2 0 0 0 0 0 1 1 2 0 0 0 1 1 1 0 1 1 2 0 2 0 1 20 0 0 0 0 0 0 0 1 1 2 0 1 0 0 0 1 0 1 0 0 0 1 0 0 20 0 2 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 20 0 1 1 2 0 0 0 2 0 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 20 0 1 0 0 0 2 0 2 0 1 1 2 0 1 1 2 0 1 1 2 0 2 0 1 2 20 0 0 0 1 1 2 0 1 0 1 0 2 0 1 1 1 0 ...
output:
? 1 aa ? 1 bb ? 3 aa ? 3 bb ? 5 aa ? 5 bb ? 7 aa ? 7 bb ? 8 ba ? 8 bc ? 10 aa ? 10 bb ? 12 aa ? 12 bb ? 13 ba ? 13 bc ? 15 aa ? 15 bb ? 16 ba ? 16 bc ? 18 aa ? 18 bb ? 19 za ? 19 zb ! bbcccccbccccbbcbcbbb ? 1 aa ? 1 bb ? 3 aa ? 3 bb ? 5 aa ? 5 bb ? 7 aa ? 7 bb ? 8 ba ? 8 bc ? 10 aa ? 10 bb ? 11 ba ?...
result:
ok max queries count: 26
Test #9:
score: 0
Accepted
time: 4ms
memory: 3520kb
input:
100 0 2 0 0 0 0 0 1 1 2 0 0 0 1 1 1 0 1 1 2 0 2 0 1 0 0 0 0 0 0 0 1 1 2 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 2 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 2 0 2 0 1 1 2 0 1 1 2 0 1 1 2 0 2 0 1 2 100 0 0 0 1 1 2 0 1 0 1 0 2 0 1 1 1 0 0 0 2 0 2 0 ...
output:
? 1 aa ? 1 bb ? 3 aa ? 3 bb ? 5 aa ? 5 bb ? 7 aa ? 7 bb ? 8 ba ? 8 bc ? 10 aa ? 10 bb ? 12 aa ? 12 bb ? 13 ba ? 13 bc ? 15 aa ? 15 bb ? 16 ba ? 16 bc ? 18 aa ? 18 bb ? 20 aa ? 20 bb ? 21 ba ? 21 zb ? 23 aa ? 23 bb ? 25 aa ? 25 bb ? 27 aa ? 27 bb ? 28 ba ? 28 bc ? 30 aa ? 30 bb ? 31 ba ? 31 zb ? 33 a...
result:
ok max queries count: 127
Test #10:
score: 0
Accepted
time: 9ms
memory: 3468kb
input:
100 0 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 2 100 1 0 2 1 0 2 1 0 2 1 0 2 1 0 ...
output:
? 1 aa ? 1 bb ? 3 aa ? 3 ba ? 4 ba ? 4 bb ? 6 aa ? 6 ba ? 7 ba ? 7 bb ? 9 aa ? 9 ba ? 10 ba ? 10 bb ? 12 aa ? 12 ba ? 13 ba ? 13 bb ? 15 aa ? 15 ba ? 16 ba ? 16 bb ? 18 aa ? 18 ba ? 19 ba ? 19 bb ? 21 aa ? 21 ba ? 22 ba ? 22 bb ? 24 aa ? 24 ba ? 25 ba ? 25 bb ? 27 aa ? 27 ba ? 28 ba ? 28 bb ? 30 aa ...
result:
ok max queries count: 134
Extra Test:
score: 0
Extra Test Passed