QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #432614 | #1813. Joy with Permutations | unputdownable | RE | 1ms | 3888kb | C++17 | 2.4kb | 2024-06-07 13:59:00 | 2024-06-07 13:59:00 |
Judging History
answer
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int>
using namespace std;
inline int read(void) {
int x=0,sgn=1; char ch=getchar();
while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
while(47<ch&&ch<58) {x=x*10+ch-48; ch=getchar();}
return sgn? x:-x;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
/*
write((Ans%p+p)%p); pls
*/
// int a[100005];
int n;
int res[100005],a1,a2,b1,b2,A,B;
inline int Ask(int x,int y,int z) {
printf("? 1 %d %d %d\n",x,y,z); fflush(stdout);
int res; scanf("%d",&res);
// res=a[x]+a[y]+a[z]-min({a[x],a[y],a[z]})-max({a[x],a[y],a[z]});
return res;
}
inline int Ask2(int x,int y) {
printf("? 2 %d %d\n",x,y); fflush(stdout);
int res; scanf("%d",&res);
// res=(a[x]<a[y] ? x : y);
return res;
}
inline void init() {
int val[4],rnk[4];
val[0]=rnk[0]=Ask(1,2,3),val[1]=rnk[1]=Ask(1,2,4),val[2]=rnk[2]=Ask(1,3,4),val[3]=rnk[3]=Ask(2,3,4);
sort(rnk,rnk+4);
A=rnk[0]; B=rnk[2];
if(val[0]==A) {
if(val[1]==A) a1=1,a2=2,b1=3,b2=4;
else if(val[2]==A) a1=1,a2=3,b1=2,b2=4;
else a1=2,a2=3,b1=1,b2=4;
} else if(val[1]==A) {
if(val[2]==A) a1=1,a2=4,b1=2,b2=3;
else a1=2,a2=4,b1=1,b2=3;
} else a1=3,a2=4,b1=1,b2=2;
}
signed main() {
// freopen("localinput","r",stdin);
// freopen("localoutput","w",stdout);
scanf("%d",&n); init();
for(int i=5; i<=n; ++i) {
int v=Ask(a1,b1,i);
if(v<A) {
res[a2]=A; A=v;
a2=i;
} else if(v==A) {
res[a1]=A;
a1=i; A=Ask(a1,a2,b1);
} else if(A<v&&v<B) {
res[i]=v;
} else if(v==B) {
res[b1]=B;
b1=i; A=Ask(a1,b1,b2);
} else if(v>B) {
res[b2]=B; B=v;
b2=i;
} else assert(0);
}
int r=Ask2(a1,a2);
res[r]=1; res[a1^a2^r]=2; assert(A==2);
r=Ask2(b1,b2);
res[r]=n-1; res[b1^b2^r]=n; assert(B==n-1);
printf("!"); for(int i=1; i<=n; ++i) printf(" %d",res[i]); printf("\n"); fflush(stdout);
// fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
5 4 3 3 4 3 2 4 3
output:
? 1 1 2 3 ? 1 1 2 4 ? 1 1 3 4 ? 1 2 3 4 ? 1 1 2 5 ? 1 5 4 2 ? 2 5 4 ? 2 2 3 ! 3 5 4 1 2
result:
ok OK (6 2)
Test #2:
score: -100
Runtime Error
input:
60000 2 2 3 3 3 4 4 4 5 5 6 6 6 7 7 8 8 8 9 9 10 10 10 11 11 12 12 12 13 13 14 14 14 15 15 16 16 16 17 17 18 18 18 19 19 20 20 20 21 21 22 22 22 23 23 24 24 24 25 25 26 26 26 27 27 28 28 28 29 29 30 30 30 31 31 32 32 32 33 33 34 34 34 35 35 36 36 36 37 37 38 38 38 39 39 40 40 40 41 41 42 42 42 43 43...
output:
? 1 1 2 3 ? 1 1 2 4 ? 1 1 3 4 ? 1 2 3 4 ? 1 1 3 5 ? 1 1 5 4 ? 1 1 5 6 ? 1 6 2 5 ? 1 6 5 7 ? 1 6 5 8 ? 1 6 8 7 ? 1 6 8 9 ? 1 9 2 8 ? 1 9 8 10 ? 1 9 8 11 ? 1 9 11 10 ? 1 9 11 12 ? 1 12 2 11 ? 1 12 11 13 ? 1 12 11 14 ? 1 12 14 13 ? 1 12 14 15 ? 1 15 2 14 ? 1 15 14 16 ? 1 15 14 17 ? 1 15 17 16 ? 1 15 17...