QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461248#8490. Guess the StringLynkcat#AC ✓39ms3760kbC++145.6kb2024-07-02 17:12:372024-07-02 17:12:38

Judging History

This is the latest submission verdict.

  • [2024-07-02 17:12:38]
  • Judged
  • Verdict: AC
  • Time: 39ms
  • Memory: 3760kb
Show
  • [2024-07-02 17:12:37]
  • Submitted

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
const int N=1005;
int n,a[N],b[N];
int qry(int u,int x,int y)
{
    cout<<"? "<<u<<" "<<char('a'+x)<<char('a'+y)<<endl;
    int res=(b[u]==x)+(b[u+1]==y);
    cin>>res;
    return res;
}
void guess(int x,int y)
{
    int t=qry(x,0,0);
    if (t==0)
    {
        int t=qry(x,1,1);
        if (t==0) 
        {
            a[x]=2,a[y]=2;
            return;
        }
        if (t==1)
        {
            int t=qry(x,1,2);
            if (t==0) 
            {
                a[x]=2,a[y]=1;
                return;
            }
            a[x]=1,a[y]=2;
            return;
        }
        a[x]=1,a[y]=1;
        return;
    }
    if (t==1)
    {
        int t=qry(x,0,1);
        if (t==0)
        {
            a[y]=0;
            int t=qry(x,1,0);
            if (t==2) a[x]=1; else a[x]=2;
            return;
        }
        if (t==1)
        {
            a[x]=0;a[y]=2;
            return;
        }
        a[x]=0,a[y]=1;
        return;
    }
    a[x]=0,a[y]=0;
    return;
}
void guess(int x,int y,int z)
{
    int t=qry(x,0,0);
    if (t==0)
    {
        int t=qry(x,1,1);
        if (t==0) 
        {
            a[x]=2,a[y]=2;
            int t=qry(y,2,0);
            if (t==1)
            {
                int t=qry(y,2,1);
                if (t==2) 
                {
                    a[z]=1;
                    return;
                }
                a[z]=2;
                return;
            }
            a[z]=0;
            return;
        }
        if (t==1)
        {
            int t=qry(y,1,0);
            if (t==0)
            {
                a[x]=1,a[y]=2;
                int t=qry(y,2,1);
                if (t==2)
                {
                    a[z]=1;
                    return;
                }
                a[z]=2;
                return;
            }
            if (t==1)
            {
                int t=qry(y,1,1);
                if (t==0)
                {
                    a[x]=1,a[y]=2;
                    a[z]=0;
                    return;
                }
                if (t==1)
                {
                    a[x]=2,a[y]=1;
                    a[z]=2;
                    return;
                }
                if (t==2)
                {
                    a[x]=2,a[y]=1,a[z]=1;
                    return;
                }
            }
            if (t==2)
            {
                a[x]=2,a[y]=1,a[z]=0;
                return;
            }
            return;
        }
        if (t==2)
        {
            a[x]=1,a[y]=1;
            int t=qry(y,1,0);
            if (t==2)
            {
                a[z]=0;
                return;
            }
            t=qry(y,1,1);
            if (t==2)
            {
                a[z]=1;
                return;
            }
            a[z]=2;
            return;
        }
    }
    if (t==1)
    {
        int t=qry(y,0,0);
        if (t==0)
        {
            a[x]=0;
            int t=qry(x,0,1);
            if (t==2) a[y]=1;
            else a[y]=2;
            
            t=qry(y,a[y],1);
            if (t==2) a[z]=1;
            else a[z]=2;
            return;
        }
        if (t==1)
        {
            int t=qry(y,0,1);
            if (t==0)
            {
                a[x]=0;a[z]=0;
                int t=qry(x,0,1);
                if (t==2) a[y]=1;
                else a[y]=2;
                return;
            }
            if (t==1)
            {
                a[y]=0;
                a[z]=2;
                int t=qry(x,1,0);
                if (t==2) a[x]=1;
                else a[x]=2;
                return;
            }
            if (t==2)
            {
                a[y]=0,a[z]=1;
                int t=qry(x,1,0);
                if (t==2) a[x]=1;
                else a[x]=2;
                return;
            }
        }
        if (t==2)
        {
            a[y]=0,a[z]=0;
            int t=qry(x,1,0);
            if (t==2) a[x]=1;
            else a[x]=2;
            return;
        }
    }
    if (t==2)
    {
        a[x]=a[y]=0;
        int t=qry(y,0,0);
        if (t==2)
        {
            a[z]=0;
            return;
        }
        t=qry(y,0,1); 
        if (t==2)
        {
            a[z]=1;
            return;
        }
        a[z]=2;
        return;
    }
    return;
}
mt19937_64 rnd(time(0));
void BellaKira()
{
    for (int i=1;i<=n;i++) b[i]=rnd()%3;
    for (int i=1;i<=n;i+=3)
    {
        if (i+1>n)
        {
            int t=qry(i-1,a[i-1],0);
            if (t==2) a[i]=0;
            else
            {
                t=qry(i-1,a[i-1],1);
                if (t==2) a[i]=1;
                else a[i]=2;
            }
            break;
        }
        if (i+2>n)
        {
            guess(i,i+1);
            break;
        }
        guess(i,i+1,i+2);
    }
    // for (int i=1;i<=n;i++)
    // {
    //     if (a[i]!=b[i]) cout<<"!!"<<i<<" "<<a[i]<<" "<<b[i]<<endl;
    //     assert(a[i]==b[i]);
    // }
    cout<<"! ";
    for (int i=1;i<=n;i++) cout<<char('a'+a[i]);
    cout<<endl;
}
signed main()
{
	int T=1;
	while (cin>>n)
	{
		BellaKira();
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3744kb

input:

3
1
0
2
1
0

output:

? 1 aa
? 2 aa
? 1 ab
? 2 bb
! abc
!

result:

ok max queries count: 4

Test #2:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

2
2
2
1
2
2
1
0
2
2
0
1
0
2
0
2
2
1
0
1
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 ba
! ba
? 1 aa
? 1 bb
? 1 bc
! cb
? 1 aa
? 1 bb
! bb
? 1 aa
? 1 ab
? 1 ba
! 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: 3676kb

input:

3
1
0
1
2
3
1
1
0
2
3
1
2
2
3
0
1
2
3
0
1
0
1
3
0
0
1
1
3
1
1
2
1
3
1
1
1
2
3
0
1
1
2
3
0
1
0
2
3
1
0
1
1
3
0
0
1
2
3
1
0
2
1
3
0
1
1
1
3
0
0
2
3
2
2
3
0
1
1
0
3
1
1
1
1
3
1
1
2
2
3
0
2
1
2
3
2
1
2
3
1
2
1
3
0
2
1
1
3
1
1
0
1
3
0
2
2
3
2
1
1
3
1
0
2
2
0

output:

? 1 aa
? 2 aa
? 1 ab
? 2 cb
! acb
? 1 aa
? 2 aa
? 2 ab
? 1 ab
! aba
? 1 aa
? 2 aa
? 1 ba
! baa
? 1 aa
? 1 bb
? 2 ba
! cba
? 1 aa
? 1 bb
? 2 ba
? 2 cb
! bcc
? 1 aa
? 1 bb
? 2 ca
? 2 cb
! ccc
? 1 aa
? 2 aa
? 2 ab
? 1 ba
! cab
? 1 aa
? 2 aa
? 2 ab
? 1 ba
! bac
? 1 aa
? 1 bb
? 2 ba
? 2 bb
! cbb
? 1 aa
?...

result:

ok max queries count: 4

Test #4:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

4
1
0
1
2
2
4
1
1
2
2
1
1
4
1
2
2
2
4
1
0
2
1
1
1
4
0
1
2
1
1
4
0
0
1
1
2
4
1
1
1
2
1
1
4
0
2
2
1
1
4
0
0
1
1
1
1
4
0
1
0
2
2
4
1
1
0
2
1
1
4
2
2
1
2
4
0
1
1
0
1
1
4
0
1
1
1
2
4
1
0
2
1
1
2
4
1
1
1
1
1
1
4
0
1
1
0
2
4
0
1
0
2
1
2
4
0
1
1
2
1
2
4
0
1
0
1
1
2
4
2
1
2
2
4
0
1
1
1
1
1
4
1
1
0
1
1
2
4
0
...

output:

? 1 aa
? 2 aa
? 1 ab
? 2 cb
? 3 ba
! acba
? 1 aa
? 2 aa
? 2 ab
? 1 ba
? 3 ba
? 3 bb
! babc
? 1 aa
? 2 aa
? 1 ba
? 3 aa
! baaa
? 1 aa
? 2 aa
? 1 ab
? 2 bb
? 3 ca
? 3 cb
! abcc
? 1 aa
? 1 bb
? 2 ba
? 3 aa
? 3 ab
! cbac
? 1 aa
? 1 bb
? 2 ca
? 2 cb
? 3 ca
! ccca
? 1 aa
? 2 aa
? 2 ab
? 1 ba
? 3 ca
? 3 cb...

result:

ok max queries count: 6

Test #5:

score: 0
Accepted
time: 39ms
memory: 3668kb

input:

100
0
2
1
1
2
1
1
1
1
0
1
2
2
1
0
1
1
0
1
1
0
1
0
1
1
0
1
2
0
1
0
2
1
2
1
0
2
1
2
1
2
1
0
0
1
1
1
1
1
1
2
1
1
0
1
1
0
1
0
2
1
0
1
2
1
2
1
1
0
2
1
0
1
1
1
1
2
1
0
2
1
2
2
1
1
2
1
2
1
1
1
2
0
0
1
2
2
1
2
1
0
2
1
0
0
1
2
0
1
0
1
0
1
0
2
1
0
1
1
1
1
100
0
2
1
1
1
0
1
2
0
1
1
1
1
0
2
2
1
1
0
2
0
0
1
1
0
...

output:

? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
? 5 aa
? 5 ab
? 7 aa
? 8 aa
? 8 ab
? 7 ab
? 10 aa
? 11 aa
? 13 aa
? 14 aa
? 13 ab
? 14 cb
? 16 aa
? 16 bb
? 17 ba
? 17 bb
? 19 aa
? 20 aa
? 19 ab
? 20 cb
? 22 aa
? 22 bb
? 23 ba
? 25 aa
? 25 bb
? 26 ba
? 26 cb
? 28 aa
? 29 aa
? 28 ba
? 31 aa
? 31 bb
? 32 ba
? 32 bb...

result:

ok max queries count: 129

Test #6:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

4
0
2
1
1
2
4
1
1
0
1
1
1
4
2
2
2
4
1
0
1
1
1
2
4
1
2
1
1
1
4
0
0
1
2
2
4
0
1
0
2
1
1
4
2
1
2
1
2
4
0
1
1
0
2
4
0
0
1
1
1
1
4
1
1
0
1
2
4
0
1
1
1
2
4
1
0
2
1
1
1
4
1
1
1
2
2
4
2
1
2
1
1
4
0
1
1
1
1
1
4
2
1
2
1
2
4
1
2
2
1
1
4
2
1
2
1
2
4
1
0
1
1
1
1
4
1
2
2
1
2
4
1
0
2
1
1
1
4
0
1
1
2
1
1
4
0
1
1
1
...

output:

? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 3 ca
! bbca
? 1 aa
? 2 aa
? 2 ab
? 1 ab
? 3 aa
? 3 ab
! acac
? 1 aa
? 2 aa
? 3 aa
! aaaa
? 1 aa
? 2 aa
? 1 ab
? 2 cb
? 3 ca
? 3 cb
! accb
? 1 aa
? 2 aa
? 1 ba
? 3 aa
? 3 ab
! caac
? 1 aa
? 1 bb
? 2 ca
? 2 cb
? 3 ba
! ccba
? 1 aa
? 1 bb
? 2 ba
? 2 cb
? 3 ba
? 3 bb
! bcbc...

result:

ok max queries count: 6

Test #7:

score: 0
Accepted
time: 4ms
memory: 3760kb

input:

5
0
2
1
1
2
5
1
1
1
1
2
5
2
2
0
0
5
0
1
1
0
1
1
5
0
0
1
2
1
2
5
0
1
1
1
2
5
0
2
1
2
1
0
1
5
1
0
1
1
0
0
5
1
1
0
1
1
1
5
0
1
1
0
1
2
5
0
0
1
2
1
1
5
2
2
0
1
2
5
0
1
1
1
1
0
1
5
1
0
2
2
1
0
2
5
1
1
0
1
1
2
5
1
1
1
2
0
0
5
1
2
2
1
0
2
5
0
1
0
1
0
1
0
5
0
1
0
1
0
1
2
5
1
1
1
2
0
0
5
0
2
1
1
1
1
5
0
1
0
...

output:

? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
! bbcaa
? 1 aa
? 2 aa
? 2 ab
? 1 ba
? 4 aa
! cacaa
? 1 aa
? 2 aa
? 4 aa
? 4 bb
! aaacc
? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
? 4 ab
! bcaac
? 1 aa
? 1 bb
? 2 ca
? 2 cb
? 4 aa
? 4 ab
! ccbab
? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
! cbcaa
? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
...

result:

ok max queries count: 7

Test #8:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

20
0
2
1
1
0
0
1
1
0
1
1
1
0
0
1
1
0
2
1
1
0
1
0
2
0
2
20
0
0
1
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
0
2
0
0
1
2
0
0
20
0
2
1
2
0
1
1
2
0
0
1
1
0
2
1
2
0
0
1
1
0
2
1
1
0
1
0
20
0
1
1
1
0
0
1
2
0
1
0
1
0
1
0
2
0
1
1
2
0
1
0
1
0
1
0
20
0
1
0
1
0
2
1
2
0
1
0
2
0
0
1
2
0
0
1
2
0
1
1
2
0
1
2
20
0
0
1
1
0
1
0
2
...

output:

? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
? 4 bb
? 5 ca
? 5 cb
? 7 aa
? 7 bb
? 8 ba
? 8 bb
? 10 aa
? 10 bb
? 11 ca
? 11 cb
? 13 aa
? 13 bb
? 14 ba
? 14 bb
? 16 aa
? 16 bb
? 17 ba
? 17 cb
? 19 aa
? 19 bb
! bbcccccbccccbbcbcbbb
? 1 aa
? 1 bb
? 2 ca
? 2 cb
? 4 aa
? 4 bb
? 5 ca
? 5 cb
? 7 aa
? 7 bb
? 8 ba
? 8 ...

result:

ok max queries count: 27

Test #9:

score: 0
Accepted
time: 13ms
memory: 3628kb

input:

100
0
2
1
1
0
0
1
1
0
1
1
1
0
0
1
1
0
2
1
1
0
1
0
2
0
2
1
1
0
0
1
1
0
0
1
1
0
1
0
2
0
0
1
2
0
1
1
1
0
1
1
1
0
1
1
2
0
1
0
2
0
1
0
1
0
1
1
2
0
1
0
1
0
1
1
2
0
0
1
2
0
1
1
1
0
0
1
2
0
1
0
1
0
1
0
2
0
1
1
2
0
1
0
1
0
1
1
2
0
0
1
2
0
2
1
2
0
1
1
1
0
1
1
1
0
1
1
1
0
2
1
2
1
1
100
0
0
1
1
0
1
0
2
0
1
1
2
...

output:

? 1 aa
? 1 bb
? 2 ba
? 2 bb
? 4 aa
? 4 bb
? 5 ca
? 5 cb
? 7 aa
? 7 bb
? 8 ba
? 8 bb
? 10 aa
? 10 bb
? 11 ca
? 11 cb
? 13 aa
? 13 bb
? 14 ba
? 14 bb
? 16 aa
? 16 bb
? 17 ba
? 17 cb
? 19 aa
? 19 bb
? 20 ba
? 20 bb
? 22 aa
? 22 bb
? 23 ca
? 23 cb
? 25 aa
? 25 bb
? 26 ca
? 26 cb
? 28 aa
? 28 bb
? 29 ba
...

result:

ok max queries count: 134

Test #10:

score: 0
Accepted
time: 10ms
memory: 3756kb

input:

100
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
0
2
2
1
2
100
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
1
0
2
1
...

output:

? 1 aa
? 1 bb
? 2 ba
? 4 aa
? 4 bb
? 5 ba
? 7 aa
? 7 bb
? 8 ba
? 10 aa
? 10 bb
? 11 ba
? 13 aa
? 13 bb
? 14 ba
? 16 aa
? 16 bb
? 17 ba
? 19 aa
? 19 bb
? 20 ba
? 22 aa
? 22 bb
? 23 ba
? 25 aa
? 25 bb
? 26 ba
? 28 aa
? 28 bb
? 29 ba
? 31 aa
? 31 bb
? 32 ba
? 34 aa
? 34 bb
? 35 ba
? 37 aa
? 37 bb
? 38 ...

result:

ok max queries count: 134

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-04-08 22:05:54 | OpenSource Project