QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244756#6303. Inversionhhoppitree#WA 70ms19592kbC++141.7kb2023-11-09 15:24:182023-11-09 15:24:19

Judging History

你现在查看的是最新测评结果

  • [2023-11-09 15:24:19]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:19592kb
  • [2023-11-09 15:24:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int via[N][N];
__inline int ask(int l,int r)
{
    if(l==r)return 0;
    if(l>r) return 0;
    if(via[l][r]!=-1)return via[l][r];
    printf("? %d %d\n",l,r);fflush(stdout);
    scanf("%d",&via[l][r]);return via[l][r];
}
__inline int cmp(int x,int y)
//ask if p_i>p_j
{
    int op=0;if(x>y)swap(x,y),op=1;
    return (ask(x,y)+ask(x+1,y-1)-ask(x,y-1)-ask(x+1,y)+10+op)%2;
}
int p[N],ip[N];
int main()
{
    int n;
    memset(via,-1,sizeof via);
    scanf("%d",&n);
    p[1]=1;
    for(int i=2;i<=n;++i)
    {
        // cerr<<"SOLVED : ";
        // for(int j=1;j<i;++j)cerr<<p[j]<<"_";cerr<<endl;
        for(int j=1;j<i;++j)ip[p[j]]=j;
        int u=(ask(1,i)-ask(1,i-1)+2)%2;
        vector<int>mb;
        // cerr<<"DELTA="<<u<<endl;
        for(int j=1;j<i;++j)if((i-j&1)==u)mb.push_back(ip[j]);
        //mb: greater than j
        int l=0,r=(int)mb.size()-1,ans=mb.size();
        // for(int i:mb)cerr<<i<<",";cerr<<endl;
        while(l<=r)
        {
            int mid=l+r>>1;
            // cerr<<"TRY : "<<mb[mid]<<endl;
            if(cmp(mb[mid],i))//p_{mb_mid}>p_i
            {
                // cerr<<"SUC,LESS\n";
                ans=mid,r=mid-1;
            }
            else
                // cerr<<"FAI,GREATER\n", 
                l=mid+1;
        }
        // cerr<<"ENDIN :  "<<ans<<endl;
        if(ans==mb.size())
        {
            p[i]=i;
        }
        else
        {
            int pos=mb[ans],w=p[pos];
            // cerr<<"END IN : "<<pos<<endl;
            for(int j=1;j<i;++j)if(p[j]>=w)++p[j];
            p[i]=w;
        }
    }
    printf("!");
    for(int i=1;i<=n;++i)printf(" %d",p[i]);puts("");
    return 0;
}

详细

Test #1:

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

input:

3
0
0
1

output:

? 1 2
? 1 3
? 2 3
! 2 3 1

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 70ms
memory: 19576kb

input:

1993
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
1
1
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
0
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
0
0
0
1
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0...

output:

? 1 2
? 1 3
? 2 3
? 1 4
? 2 4
? 3 4
? 1 5
? 2 5
? 1 6
? 2 6
? 1 7
? 2 7
? 5 7
? 5 6
? 6 7
? 1 8
? 2 8
? 3 8
? 4 7
? 3 7
? 4 8
? 1 9
? 6 9
? 7 8
? 6 8
? 7 9
? 2 9
? 3 9
? 1 10
? 2 10
? 5 10
? 5 9
? 6 10
? 1 11
? 9 11
? 9 10
? 10 11
? 6 11
? 7 10
? 7 11
? 1 12
? 2 11
? 2 12
? 8 12
? 8 11
? 9 12
? 10 1...

result:

wrong output format Unexpected end of file - int32 expected