QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #805029 | #1458. Binary Search Algorithm | Invincible | WA | 8ms | 3892kb | C++23 | 2.8kb | 2024-12-08 11:57:13 | 2024-12-08 11:57:14 |
Judging History
answer
//9:32
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
//#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
int s = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return f ? s : -s;
}
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(x>y)x=y;}
const int N=8005;
int n,cnt,a[N],id[N],stk[N],rk[N],top;
char op[10];
void Swap(int x,int y){
id[a[x]]=y,id[a[y]]=x;
swap(a[x],a[y]);
}
void add(int x){
cnt++;
a[cnt]=x,id[x]=cnt;
int pos=cnt;
int now=pos;
top=0;
while(now){
stk[++top]=now;
if((now>>1)&&(now^1)<=cnt)stk[++top]=now^1;
now>>=1;
}
printf("%d ",top);
rep(i,1,top)printf("%d%c",a[stk[i]]," \n"[i==top]);
fflush(stdout);
rep(i,1,top)rk[read()]=i;
now=pos;
while(now>1&&rk[a[now>>1]]>rk[a[now]]){
Swap(now,now>>1);
now>>=1;
}
int u=pos;
while(u>=now&&u>1){
if(u&1){
if(rk[a[u^1]]>rk[a[u]])Swap(u,u^1);
}else{
if((u^1)<=cnt&&rk[a[u]]>rk[a[u^1]])Swap(u,u^1);
}
u>>=1;
}
}
void del(int x){
if(id[x]==cnt)return cout<<0<<endl,cnt--,void();
int pos=id[x];
Swap(cnt,id[x]);
cnt--;
int now=pos;
top=0;
while(now<=cnt){
stk[++top]=now;
if((now<<1|1)<=cnt)stk[++top]=now<<1|1;
now<<=1;
}
printf("%d ",top);
rep(i,1,top)printf("%d%c",a[stk[i]]," \n"[i==top]);
fflush(stdout);
rep(i,1,top)rk[read()]=i;
now=pos;
while((now<<1)<=cnt&&rk[a[now<<1]]<rk[a[now]]){
Swap(now,now<<1);
now<<=1;
}
while(now>=pos){
if(now>1&&(now^1)<=cnt&&rk[a[now]]>rk[a[now^1]])Swap(now,now^1);
now>>=1;
}
}
bool Med;
signed main() {
fprintf(stderr,"%.3lfMb\n",(&Mbe-&Med)/1024./1024.);
n=read();
int now=0;
for(int T=n+n;T--;){
scanf("%s",op);
int x=read();
if(++now==1908){
assert(x==a[1]);
}
if(op[0]=='a')add(x);
else del(x);
if(!cnt)printf("-1\n");
else printf("%d\n",a[1]);
fflush(stdout);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
input:
3 add 1 1 add 3 3 1 delete 1 add 2 3 2 delete 3 2 delete 2
output:
1 1 1 2 3 1 3 0 3 2 2 3 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
10 add 9 9 add 4 9 4 add 6 9 4 6 delete 9 4 6 add 7 7 4 6 delete 4 6 add 5 7 5 6 add 8 7 5 8 6 add 10 7 10 5 8 6 delete 8 add 3 3 7 10 5 6 add 2 3 7 6 2 delete 6 2 delete 10 5 delete 7 5 add 1 3 1 5 2 delete 1 5 delete 3 5 2 delete 5 2 delete 2
output:
1 9 9 2 4 9 9 3 6 4 9 9 2 6 4 4 3 7 6 4 7 1 6 7 3 5 6 7 7 4 8 5 6 7 7 5 10 8 5 6 7 7 0 7 5 3 5 10 6 7 3 4 2 6 7 3 3 1 2 3 1 5 3 1 5 3 4 1 5 2 3 3 1 5 3 2 2 5 5 1 2 2 0 -1
result:
ok n=10, OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
100 add 81 81 add 96 81 96 add 94 81 94 96 add 32 81 94 32 96 add 35 81 94 32 35 96 add 59 81 94 59 96 add 50 81 50 94 59 96 add 57 81 50 57 94 32 35 add 39 39 81 50 57 94 32 35 add 55 39 81 50 94 35 55 add 23 39 81 50 94 23 35 55 add 40 39 81 40 94 59 96 add 5 39 81 40 94 59 96 5 add 2 39 81 40 94 ...
output:
1 81 81 2 96 81 81 3 94 96 81 81 4 32 94 96 81 81 5 35 32 94 96 81 81 4 59 96 94 81 81 5 50 96 59 94 81 81 6 57 32 35 50 94 81 81 7 39 32 57 35 50 94 81 39 6 55 35 50 81 94 39 39 7 23 55 35 50 81 94 39 39 6 40 59 96 94 81 39 39 7 5 59 94 96 40 81 39 39 6 2 96 94 40 81 39 39 1 2 39 6 12 96 94 40 81 3...
result:
ok n=100, OK
Test #4:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
100 add 71 71 add 75 71 75 add 43 43 71 75 add 69 43 71 69 75 add 55 43 71 69 55 75 add 89 43 71 89 75 add 31 43 71 89 31 75 add 52 43 71 89 69 55 52 add 24 24 43 71 89 69 55 52 add 6 24 43 71 89 6 55 add 9 24 43 71 89 6 55 9 add 62 24 43 89 62 31 75 add 19 24 43 89 62 31 75 19 add 35 24 43 35 89 62...
output:
1 71 71 2 75 71 71 3 43 75 71 43 4 69 71 75 43 43 5 55 69 71 75 43 43 4 89 75 71 43 43 5 31 75 89 71 43 43 6 52 69 55 71 89 43 43 7 24 52 69 55 71 89 43 24 6 6 55 71 43 89 24 24 7 9 55 6 71 43 89 24 24 6 62 31 75 89 43 24 24 7 19 31 62 75 89 43 24 24 6 35 75 62 89 43 24 24 7 38 75 62 89 35 43 24 24 ...
result:
ok n=100, OK
Test #5:
score: -100
Wrong Answer
time: 8ms
memory: 3892kb
input:
1000 add 93 93 add 917 93 917 add 921 93 917 921 add 70 93 917 921 70 add 949 93 949 917 921 70 add 777 93 949 777 921 add 237 93 949 777 237 921 add 581 581 93 949 777 917 70 add 461 581 93 949 777 917 70 461 add 319 581 93 949 777 319 70 add 42 581 93 949 777 42 319 70 add 690 581 93 690 777 237 9...
output:
1 93 93 2 917 93 93 3 921 917 93 93 4 70 917 921 93 93 5 949 70 917 921 93 93 4 777 921 949 93 93 5 237 921 777 949 93 93 6 581 917 70 949 777 93 581 7 461 917 949 70 93 777 581 581 6 319 70 949 93 777 581 581 7 42 70 319 949 93 777 581 581 6 690 237 921 777 93 581 581 7 631 237 777 921 690 93 581 5...
result:
wrong answer WA after query 1908 found 412, answer is 11