QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203590 | #7535. Limited Shuffle Restoring | 275307894a | WA | 1ms | 4000kb | C++14 | 1.4kb | 2023-10-06 18:27:12 | 2023-10-06 18:27:12 |
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;return f[make_pair(x,y)]=(c=='<');
}
int A[N];
void Solve(){
cin>>n;
if(n==1){cout<<"! 1"<<endl;return;}
int i1=n-1,i2=n;
for(int i=n;i>2;i--){
int p=i-2;
int o1=ask(p,i1),o2=ask(p,i2),o3=ask(i1,i2);
if(o1&&o2&&i>3){
if(o3) A[i2]=i,A[i1]=i-1;else A[i1]=i,A[i2]=i-1;
i2=p;i1=i-3;i--;continue;
}
if(!o1&&!o2)A[p]=i;
else if(o3&&o2) A[i2]=i,i2=i1,i1=p;
else A[i1]=i,i1=p;
}
if(ask(i1,i2)) A[i1]=1,A[i2]=2;
else A[i1]=2,A[i2]=1;
cout<<"! ";for(int i=1;i<=n;i++) cout<<A[i]<<' ';cout<<endl;
}
int main(){
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: 1ms
memory: 3936kb
input:
5 < < > < > >
output:
? 3 4 ? 3 5 ? 4 5 ? 1 2 ? 1 3 ? 2 3 ! 2 3 1 5 4
result:
ok yeah, seems ok, spent 6 queries of 13
Test #2:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 0ms
memory: 3940kb
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: 3988kb
input:
3 > > >
output:
? 1 2 ? 1 3 ? 2 3 ! 3 2 1
result:
ok yeah, seems ok, spent 3 queries of 10
Test #5:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
4 > > > < >
output:
? 2 3 ? 2 4 ? 3 4 ? 1 3 ? 1 4 ! 2 4 3 1
result:
ok yeah, seems ok, spent 5 queries of 11
Test #6:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
5 > > > < > < >
output:
? 3 4 ? 3 5 ? 4 5 ? 2 4 ? 2 5 ? 1 2 ? 1 5 ! 2 3 5 4 1
result:
ok yeah, seems ok, spent 7 queries of 13
Test #7:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
6 > > > < > < > < >
output:
? 4 5 ? 4 6 ? 5 6 ? 3 5 ? 3 6 ? 2 3 ? 2 6 ? 1 2 ? 1 6 ! 2 3 4 6 5 1
result:
ok yeah, seems ok, spent 9 queries of 15
Test #8:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
7 > > > < > < > < > < >
output:
? 5 6 ? 5 7 ? 6 7 ? 4 6 ? 4 7 ? 3 4 ? 3 7 ? 2 3 ? 2 7 ? 1 2 ? 1 7 ! 2 3 4 5 7 6 1
result:
ok yeah, seems ok, spent 11 queries of 16
Test #9:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
8 > > > < > < > < > < > < >
output:
? 6 7 ? 6 8 ? 7 8 ? 5 7 ? 5 8 ? 4 5 ? 4 8 ? 3 4 ? 3 8 ? 2 3 ? 2 8 ? 1 2 ? 1 8 ! 2 3 4 5 6 8 7 1
result:
ok yeah, seems ok, spent 13 queries of 18
Test #10:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
9 > > > < > < > < > < > < > < >
output:
? 7 8 ? 7 9 ? 8 9 ? 6 8 ? 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 9 8 1
result:
ok yeah, seems ok, spent 15 queries of 20
Test #11:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
10 > > > < > < > < > < > < > < > < >
output:
? 8 9 ? 8 10 ? 9 10 ? 7 9 ? 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 10 9 1
result:
ok yeah, seems ok, spent 17 queries of 21
Test #12:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
11 > > > < > < > < > < > < > < > < > < >
output:
? 9 10 ? 9 11 ? 10 11 ? 8 10 ? 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 11 10 1
result:
ok yeah, seems ok, spent 19 queries of 23
Test #13:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
12 > > > < > < > < > < > < > < > < > < > < >
output:
? 10 11 ? 10 12 ? 11 12 ? 9 11 ? 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 12 11 1
result:
ok yeah, seems ok, spent 21 queries of 25
Test #14:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
13 > > > < > < > < > < > < > < > < > < > < > < >
output:
? 11 12 ? 11 13 ? 12 13 ? 10 12 ? 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 13 12 1
result:
ok yeah, seems ok, spent 23 queries of 26
Test #15:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
14 > > > < > < > < > < > < > < > < > < > < > < > < >
output:
? 12 13 ? 12 14 ? 13 14 ? 11 13 ? 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 14 13 1
result:
ok yeah, seems ok, spent 25 queries of 28
Test #16:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
15 > > > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 13 14 ? 13 15 ? 14 15 ? 12 14 ? 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 15 14 1
result:
ok yeah, seems ok, spent 27 queries of 30
Test #17:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
16 > > > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 14 15 ? 14 16 ? 15 16 ? 13 15 ? 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 16 15 1
result:
ok yeah, seems ok, spent 29 queries of 31
Test #18:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
17 > > > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 15 16 ? 15 17 ? 16 17 ? 14 16 ? 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 17 16 1
result:
ok yeah, seems ok, spent 31 queries of 33
Test #19:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
18 > > > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 16 17 ? 16 18 ? 17 18 ? 15 17 ? 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 18 17 1
result:
ok yeah, seems ok, spent 33 queries of 35
Test #20:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
19 > > > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < >
output:
? 17 18 ? 17 19 ? 18 19 ? 16 18 ? 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 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 ? 18 20 ? 19 20 ? 17 19 ? 17 20 ? 16 17 ? 16 20 ? 15 16 ? 15 20 ? 14 15 ? 14 20 ? 13 14 ? 13 20 ? 12 13 ? 12 20 ? 11 12 ? 11 20 ? 10 11 ? 10 20 ? 9 10 ? 9 20 ? 8 9 ? 8 20 ? 7 8 ? 7 20 ? 6 7 ? 6 20 ? 5 6 ? 5 20 ? 4 5 ? 4 20 ? 3 4 ? 3 20 ? 2 3 ? 2 20 ? 1 2 ? 1 20 ! 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: 0ms
memory: 4000kb
input:
111 < < < < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < < > < > > < > < > < > < > < > < > < > < > < > < ...
output:
? 109 110 ? 109 111 ? 110 111 ? 107 108 ? 107 109 ? 108 109 ? 105 106 ? 105 107 ? 106 107 ? 103 104 ? 103 105 ? 104 105 ? 101 102 ? 101 103 ? 102 103 ? 99 100 ? 99 101 ? 100 101 ? 97 98 ? 97 99 ? 98 99 ? 95 96 ? 95 97 ? 96 97 ? 93 94 ? 93 95 ? 94 95 ? 91 92 ? 91 93 ? 92 93 ? 89 90 ? 89 91 ? 90 91 ? ...
result:
wrong answer this is not the only answer, for example, we could have guessed [2, 3, 4, 5, 6, 7, 8, 9, 10, 1..., 107, 106, 110, 108, 109, 111]