QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#745728#6303. Inversiondezex#WA 50ms5572kbC++201.6kb2024-11-14 11:16:092024-11-14 11:16:10

Judging History

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

  • [2024-11-14 11:16:10]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:5572kb
  • [2024-11-14 11:16:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define forw(_,l,r) for(auto _=(l);_<(r);++_)
#define fors(_,r,l) for(auto _=(r);_>(l);--_)
#define RN return

typedef long long ll;
typedef vector<int> vi;
unordered_map<int,char> mp;
int cnt=0;

char ask(int l,int r){
    if(l>=r)RN 0;
    int idx=l*65536+r;
    if(l<r && mp.find(idx)==mp.end()){
        cout<<"? "<<l<<' '<<r<<'\n';
        cout.flush();
        int ret;
        cin>>ret;
        RN mp[idx]=ret;
    }
    else RN mp[idx];
}

int comp(int i,int j){
    RN ask(i,j)^ask(i+1,j)^ask(i,j-1)^ask(i+1,j-1);
}

const int NUM=2010;
int arr[NUM]={};
vi merge(int l,int r){
    // cout<<"----"<<l<<' '<<r<<endl;
    if(r<l)assert(0);
    if(r-l==0)RN {l};
    if(r-l==1){
        if(ask(l,r))RN {r,l};
        else RN {l,r};
    }
    int m=(l+r)/2;
    auto v1=merge(l,m),v2=merge(m+1,r);
    int pt1=0,pt2=0,s1=v1.size(),s2=v2.size();
    vi ret;
    while(1){
        // cout<<"why";
        if(pt1>=s1||pt2>=s2)break;
        if(comp(v1[pt1],v2[pt2])){
            ret.push_back(v2.at(pt2));
            ++pt2;
        }
        else{
            ret.push_back(v1.at(pt1));
            ++pt1;
        }
        // cout<<"pt"<<pt1<<' '<<pt2<<endl;
    }
    while(pt1<s1)ret.push_back(v1[pt1++]);
    while(pt2<s2)ret.push_back(v2[pt2++]);
    RN ret;
}

int main()
{
    int n; cin>>n;
    vi ans=merge(1,n);
    // for(auto a:ans)cout<<a<<' ';
    // RN 0;
    forw(i,0,n)arr[ans[i]]=i+1;
    cout<<"! ";
    forw(i,0,n)cout<<arr[i+1]<<' ';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 50ms
memory: 5572kb

input:

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

output:

? 1 2
? 3 4
? 1 3
? 2 3
? 5 6
? 7 8
? 5 7
? 6 7
? 5 8
? 6 8
? 1 7
? 2 7
? 1 6
? 2 6
? 1 5
? 2 5
? 1 4
? 2 4
? 1 8
? 2 8
? 3 8
? 3 7
? 4 8
? 4 7
? 9 10
? 11 12
? 10 11
? 9 11
? 9 12
? 10 12
? 13 14
? 15 16
? 14 15
? 13 15
? 13 16
? 14 16
? 10 14
? 11 14
? 10 13
? 11 13
? 12 14
? 12 13
? 11 15
? 12 15...

result:

wrong output format Unexpected end of file - int32 expected