QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#804911 | #1458. Binary Search Algorithm | Invincible | WA | 1ms | 3892kb | C++23 | 2.6kb | 2024-12-08 10:18:19 | 2024-12-08 10:18:19 |
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]<<1)>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: 1ms
memory: 3892kb
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: -100
Wrong Answer
time: 1ms
memory: 3868kb
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 add 5 7 5 4 add 8 7 5 4 8 add 10 7 10 5 4 8 delete 8 add 3 3 7 10 5 4 add 2 3 7 5 2 delete 6 2 delete 10 delete 7 10 add 1 3 10 1 2 delete 1 delete 3 10 2 delete 5 delete 2
output:
1 9 9 2 4 9 9 3 6 4 9 9 2 6 4 4 3 7 6 4 7 0 7 3 5 4 7 7 4 8 4 5 7 7 5 10 8 4 5 7 7 0 7 5 3 4 10 5 7 3 4 2 5 7 3 3 1 2 3 0 3 1 10 3 4 1 10 2 3 3 0 3 2 2 10 10 0 10 0 -1
result:
wrong answer WA in query 7 queried element 4 was not from S