QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745728 | #6303. Inversion | dezex# | WA | 50ms | 5572kb | C++20 | 1.6kb | 2024-11-14 11:16:09 | 2024-11-14 11:16:10 |
Judging History
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