QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #804915 | #1458. Binary Search Algorithm | Invincible | WA | 5ms | 3952kb | C++23 | 2.6kb | 2024-12-08 10:25:14 | 2024-12-08 10:25:15 |
Judging History
answer
#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 now=cnt;
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=cnt;
while(now>1&&rk[a[now>>1]]>rk[a[now]]){
Swap(now,now>>1);
now>>=1;
if((now<<1|1)<=cnt&&rk[a[now<<1]]>rk[a[now<<1|1]])Swap(now<<1,now<<1|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);
if((now<<1|1)<=cnt&&rk[a[now<<1]]>rk[a[now<<1|1]])Swap(now<<1,now<<1|1);
now<<=1;
}
}
bool Med;
signed main() {
fprintf(stderr,"%.3lfMb\n",(&Mbe-&Med)/1024./1024.);
n=read();
for(int T=n+n;T--;){
scanf("%s",op);
int x=read();
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: 0ms
memory: 3952kb
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: 3888kb
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 6 add 3 3 7 10 5 6 add 2 3 7 5 2 delete 6 2 delete 10 2 delete 7 2 add 1 3 1 5 2 delete 1 2 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 6 5 7 7 5 10 6 8 5 7 7 1 6 7 5 3 6 10 5 7 3 4 2 5 7 3 3 1 2 3 1 2 3 1 2 3 4 1 2 5 3 3 1 2 3 2 5 2 5 1 2 2 0 -1
result:
ok n=10, OK
Test #3:
score: -100
Wrong Answer
time: 5ms
memory: 3924kb
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 32 59 add 50 81 50 94 32 59 add 57 81 50 57 32 35 96 add 39 39 81 50 57 32 35 96 add 55 39 81 50 57 35 55 add 23 39 81 50 57 23 35 55 add 40 39 81 50 40 94 59 add 5 39 81 50 40 94 59 5 add 2 39 81 50 40 ...
output:
1 81 81 2 96 81 81 3 94 96 81 81 4 32 96 94 81 81 5 35 96 32 94 81 81 4 59 94 32 81 81 5 50 59 94 32 81 81 6 57 96 35 32 50 81 81 7 39 96 32 35 57 50 81 39 6 55 35 57 81 50 39 39 7 23 55 35 57 81 50 39 39 6 40 94 59 50 81 39 39 7 5 94 40 59 50 81 39 39 6 2 59 40 50 81 39 39 1 2 39 6 12 59 40 50 81 3...
result:
wrong answer WA after query 163 found 35, answer is 33