QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303189#6303. InversionSzyWA 55ms3908kbC++231.7kb2024-01-11 20:43:142024-01-11 20:43:14

Judging History

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

  • [2024-01-11 20:43:14]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:3908kb
  • [2024-01-11 20:43:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int n;
int p[2003],a[2003],b[2003];
int ask(int i,int j)
{
    if(i==j)return 0;
    cout<<"? "<<i<<" "<<j<<endl;
    int get;
    scanf("%d",&get);
    return get;
}
int mx(int l,int r)
{
    int f=0;
    if(l>r)
    {
        f=1;
        swap(l,r);
    }
    int v;
    if(l+1==r)v=ask(l,r);
    else v=((ask(l,r)-ask(l,r-1)-ask(l+1,r)+ask(l+1,r-1))%2+2)%2;
    return v^f;//1:pl>pr 0:pl<pr
}

/*int mx_id(int l,int r)
{
    int id=l;
    for(int i=l+1;i<=r;++i)
    {
        if(mx(id,i)==0)id=i;
    }
    return id;
}*/

void merge(int l,int r,int mid)
{
    for(int i=l;i<=r;++i)
    {
        b[i]=a[i];
    }
    int z1=l,z2=mid+1,z=l;
    while(z1<=mid&&z2<=r)
    {
        if(mx(b[z1],b[z2])==0)
        {
            a[z]=b[z1];
            ++z;
            ++z1;
        }
        else
        {
            a[z]=b[z2];
            ++z;
            ++z2;
        }
    }
    while(z1<=mid)
    {
        a[z]=b[z1];
        ++z;
        ++z1;
    }
    while(z2<=r)
    {
        a[z]=b[z2];
        ++z;
        ++z2;
    }
}

void st(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)/2;
    st(l,mid);
    st(mid+1,r);
    merge(l,r,mid);
}
void sol()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        a[i]=i;
    }
    st(1,n);
    for(int i=1;i<=n;++i)
    {
        p[a[i]]=i;
    }
    cout<<"!";
    for(int i=1;i<=n;++i)
    {
        printf(" %d",p[i]);
    }
    cout<<endl;
}
int main()
{
    int TT=1;
    //scanf("%d", &TT);
    while (TT--) sol();
    return 0;
}
/*
4
2
1 2
4
1 2
2 3
3 4
4
1 2
2 3
2 4
5
1 2
3 5
2 3
3 4
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3900kb

input:

3
0
0
0
1

output:

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

result:

ok OK, guesses=4

Test #2:

score: -100
Wrong Answer
time: 55ms
memory: 3908kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected