QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203675 | #7535. Limited Shuffle Restoring | 275307894a | WA | 2ms | 4052kb | C++14 | 1.8kb | 2023-10-06 19:22:15 | 2023-10-06 19:22:16 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e4+1,M=100+1,K=600+5,mod=1e9+7,Mod=mod-1;const db eps=1e-6;const ll INF=1e18+7;mt19937 rnd(263082);
int n;
map<pii,int> f;
int ask(int x,int y){
auto it=f.find(make_pair(x,y));if(it!=f.end()) return it->se;
char c;cout<<"? "<<x<<' '<<y<<endl;
cin>>c;
f[make_pair(x,y)]=(c=='<');
f[make_pair(y,x)]=(c!='<');
return c=='<';
}
int A[N],B[N],vis[N];
void Solve(){
cin>>n;
if(n==1){cout<<"! 1"<<endl;return;}
iota(B+1,B+n+1,1);
for(int i=n;i>2;i--) {
if(vis[i-1]&&vis[i-2]) continue;
if(vis[i-1]){
if(!ask(B[i-2],B[i])) swap(B[i-2],B[i]),vis[i-2]=1;
continue;
}
if(vis[i-2]) {
if(!ask(B[i-1],B[i])) swap(B[i-1],B[i]);
vis[i-1]=1;
}
int o1=ask(B[i-2],B[i-1]),o2=ask(B[i-1],B[i]);
if(o1&&o2) continue;
if(!o1&&!o2) {swap(B[i-2],B[i]);vis[i-1]=1;continue;}
int o3=ask(B[i-2],B[i]);
if(o1&&!o2){
if(o3){
swap(B[i-1],B[i]);vis[i-2]=vis[i-1]=1;
}else{
swap(B[i-1],B[i]);vis[i-1]=1;
}
}else{
if(o3) continue;
else swap(B[i-2],B[i]),vis[i-1]=1;
}
}
if(!ask(B[1],B[2])) swap(B[1],B[2]);
for(int i=1;i<=n;i++) A[B[i]]=i;
cout<<"! ";for(int i=1;i<=n;i++) cout<<A[i]<<' ';cout<<endl;
}
int main(){
// freopen("1.in","r",stdin);
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3988kb
input:
5 < > < < < > >
output:
? 3 4 ? 4 5 ? 3 5 ? 2 5 ? 1 2 ? 2 3 ? 1 3 ! 2 3 1 5 4
result:
ok yeah, seems ok, spent 7 queries of 13
Test #2:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
2 >
output:
? 1 2 ! 2 1
result:
ok yeah, seems ok, spent 1 queries of 8
Test #4:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
3 > < >
output:
? 1 2 ? 2 3 ? 1 3 ! 3 1 2
result:
ok yeah, seems ok, spent 3 queries of 10
Test #5:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
4 > < > < >
output:
? 2 3 ? 3 4 ? 2 4 ? 1 4 ? 1 3 ! 2 4 1 3
result:
ok yeah, seems ok, spent 5 queries of 11
Test #6:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
5 > < > < > < >
output:
? 3 4 ? 4 5 ? 3 5 ? 2 5 ? 2 4 ? 1 2 ? 1 4 ! 2 3 5 1 4
result:
ok yeah, seems ok, spent 7 queries of 13
Test #7:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
6 > < > < > < > < >
output:
? 4 5 ? 5 6 ? 4 6 ? 3 6 ? 3 5 ? 2 3 ? 2 5 ? 1 2 ? 1 5 ! 2 3 4 6 1 5
result:
ok yeah, seems ok, spent 9 queries of 15
Test #8:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
7 > < > < > < > < > < >
output:
? 5 6 ? 6 7 ? 5 7 ? 4 7 ? 4 6 ? 3 4 ? 3 6 ? 2 3 ? 2 6 ? 1 2 ? 1 6 ! 2 3 4 5 7 1 6
result:
ok yeah, seems ok, spent 11 queries of 16
Test #9:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
8 > < > < > < > < > < > < >
output:
? 6 7 ? 7 8 ? 6 8 ? 5 8 ? 5 7 ? 4 5 ? 4 7 ? 3 4 ? 3 7 ? 2 3 ? 2 7 ? 1 2 ? 1 7 ! 2 3 4 5 6 8 1 7
result:
ok yeah, seems ok, spent 13 queries of 18
Test #10:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
9 > < > < > < > < > < > < > < >
output:
? 7 8 ? 8 9 ? 7 9 ? 6 9 ? 6 8 ? 5 6 ? 5 8 ? 4 5 ? 4 8 ? 3 4 ? 3 8 ? 2 3 ? 2 8 ? 1 2 ? 1 8 ! 2 3 4 5 6 7 9 1 8
result:
ok yeah, seems ok, spent 15 queries of 20
Test #11:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
10 > < > < > < > < > < > < > < > < >
output:
? 8 9 ? 9 10 ? 8 10 ? 7 10 ? 7 9 ? 6 7 ? 6 9 ? 5 6 ? 5 9 ? 4 5 ? 4 9 ? 3 4 ? 3 9 ? 2 3 ? 2 9 ? 1 2 ? 1 9 ! 2 3 4 5 6 7 8 10 1 9
result:
ok yeah, seems ok, spent 17 queries of 21
Test #12:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
11 > < > < > < > < > < > < > < > < > < >
output:
? 9 10 ? 10 11 ? 9 11 ? 8 11 ? 8 10 ? 7 8 ? 7 10 ? 6 7 ? 6 10 ? 5 6 ? 5 10 ? 4 5 ? 4 10 ? 3 4 ? 3 10 ? 2 3 ? 2 10 ? 1 2 ? 1 10 ! 2 3 4 5 6 7 8 9 11 1 10
result:
ok yeah, seems ok, spent 19 queries of 23
Test #13:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
12 > < > < > < > < > < > < > < > < > < > < >
output:
? 10 11 ? 11 12 ? 10 12 ? 9 12 ? 9 11 ? 8 9 ? 8 11 ? 7 8 ? 7 11 ? 6 7 ? 6 11 ? 5 6 ? 5 11 ? 4 5 ? 4 11 ? 3 4 ? 3 11 ? 2 3 ? 2 11 ? 1 2 ? 1 11 ! 2 3 4 5 6 7 8 9 10 12 1 11
result:
ok yeah, seems ok, spent 21 queries of 25
Test #14:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
13 > < > < > < > < > < > < > < > < > < > < > < >
output:
? 11 12 ? 12 13 ? 11 13 ? 10 13 ? 10 12 ? 9 10 ? 9 12 ? 8 9 ? 8 12 ? 7 8 ? 7 12 ? 6 7 ? 6 12 ? 5 6 ? 5 12 ? 4 5 ? 4 12 ? 3 4 ? 3 12 ? 2 3 ? 2 12 ? 1 2 ? 1 12 ! 2 3 4 5 6 7 8 9 10 11 13 1 12
result:
ok yeah, seems ok, spent 23 queries of 26
Test #15:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
14 > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 12 13 ? 13 14 ? 12 14 ? 11 14 ? 11 13 ? 10 11 ? 10 13 ? 9 10 ? 9 13 ? 8 9 ? 8 13 ? 7 8 ? 7 13 ? 6 7 ? 6 13 ? 5 6 ? 5 13 ? 4 5 ? 4 13 ? 3 4 ? 3 13 ? 2 3 ? 2 13 ? 1 2 ? 1 13 ! 2 3 4 5 6 7 8 9 10 11 12 14 1 13
result:
ok yeah, seems ok, spent 25 queries of 28
Test #16:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
15 > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 13 14 ? 14 15 ? 13 15 ? 12 15 ? 12 14 ? 11 12 ? 11 14 ? 10 11 ? 10 14 ? 9 10 ? 9 14 ? 8 9 ? 8 14 ? 7 8 ? 7 14 ? 6 7 ? 6 14 ? 5 6 ? 5 14 ? 4 5 ? 4 14 ? 3 4 ? 3 14 ? 2 3 ? 2 14 ? 1 2 ? 1 14 ! 2 3 4 5 6 7 8 9 10 11 12 13 15 1 14
result:
ok yeah, seems ok, spent 27 queries of 30
Test #17:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
16 > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 14 15 ? 15 16 ? 14 16 ? 13 16 ? 13 15 ? 12 13 ? 12 15 ? 11 12 ? 11 15 ? 10 11 ? 10 15 ? 9 10 ? 9 15 ? 8 9 ? 8 15 ? 7 8 ? 7 15 ? 6 7 ? 6 15 ? 5 6 ? 5 15 ? 4 5 ? 4 15 ? 3 4 ? 3 15 ? 2 3 ? 2 15 ? 1 2 ? 1 15 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 16 1 15
result:
ok yeah, seems ok, spent 29 queries of 31
Test #18:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
17 > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 15 16 ? 16 17 ? 15 17 ? 14 17 ? 14 16 ? 13 14 ? 13 16 ? 12 13 ? 12 16 ? 11 12 ? 11 16 ? 10 11 ? 10 16 ? 9 10 ? 9 16 ? 8 9 ? 8 16 ? 7 8 ? 7 16 ? 6 7 ? 6 16 ? 5 6 ? 5 16 ? 4 5 ? 4 16 ? 3 4 ? 3 16 ? 2 3 ? 2 16 ? 1 2 ? 1 16 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 1 16
result:
ok yeah, seems ok, spent 31 queries of 33
Test #19:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
18 > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 16 17 ? 17 18 ? 16 18 ? 15 18 ? 15 17 ? 14 15 ? 14 17 ? 13 14 ? 13 17 ? 12 13 ? 12 17 ? 11 12 ? 11 17 ? 10 11 ? 10 17 ? 9 10 ? 9 17 ? 8 9 ? 8 17 ? 7 8 ? 7 17 ? 6 7 ? 6 17 ? 5 6 ? 5 17 ? 4 5 ? 4 17 ? 3 4 ? 3 17 ? 2 3 ? 2 17 ? 1 2 ? 1 17 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 1 17
result:
ok yeah, seems ok, spent 33 queries of 35
Test #20:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
19 > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 17 18 ? 18 19 ? 17 19 ? 16 19 ? 16 18 ? 15 16 ? 15 18 ? 14 15 ? 14 18 ? 13 14 ? 13 18 ? 12 13 ? 12 18 ? 11 12 ? 11 18 ? 10 11 ? 10 18 ? 9 10 ? 9 18 ? 8 9 ? 8 18 ? 7 8 ? 7 18 ? 6 7 ? 6 18 ? 5 6 ? 5 18 ? 4 5 ? 4 18 ? 3 4 ? 3 18 ? 2 3 ? 2 18 ? 1 2 ? 1 18 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 1...
result:
ok yeah, seems ok, spent 35 queries of 36
Test #21:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
20 > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 18 19 ? 19 20 ? 18 20 ? 17 20 ? 17 19 ? 16 17 ? 16 19 ? 15 16 ? 15 19 ? 14 15 ? 14 19 ? 13 14 ? 13 19 ? 12 13 ? 12 19 ? 11 12 ? 11 19 ? 10 11 ? 10 19 ? 9 10 ? 9 19 ? 8 9 ? 8 19 ? 7 8 ? 7 19 ? 6 7 ? 6 19 ? 5 6 ? 5 19 ? 4 5 ? 4 19 ? 3 4 ? 3 19 ? 2 3 ? 2 19 ? 1 2 ? 1 19 ! 2 3 4 5 6 7 8 9 10 11 12 13 ...
result:
ok yeah, seems ok, spent 37 queries of 38
Test #22:
score: -100
Wrong Answer
time: 2ms
memory: 4016kb
input:
111 < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < < > < < ...
output:
? 109 110 ? 110 111 ? 109 111 ? 108 111 ? 107 108 ? 108 109 ? 107 109 ? 106 109 ? 105 106 ? 106 107 ? 105 107 ? 104 107 ? 103 104 ? 104 105 ? 103 105 ? 102 105 ? 101 102 ? 102 103 ? 101 103 ? 100 103 ? 99 100 ? 100 101 ? 99 101 ? 98 101 ? 97 98 ? 98 99 ? 97 99 ? 96 99 ? 95 96 ? 96 97 ? 95 97 ? 94 97...
result:
wrong answer didn't fit into 190 queries