QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#804957#1458. Binary Search AlgorithmInvincibleWA 1ms3984kbC++232.6kb2024-12-08 11:04:142024-12-08 11:04:15

Judging History

This is the latest submission verdict.

  • [2024-12-08 11:04:15]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3984kb
  • [2024-12-08 11:04:14]
  • Submitted

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 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);
		now<<=1;
	}
	while(now>pos){
		if(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();
	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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3932kb

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: 3984kb

input:

10
add 9
9
add 4
9 4
add 6
9 4 6
delete 9
4 6
add 7
7 9 4
delete 4

add 5
7 9 5
add 8
7 9 5 8
add 10
7 10 9 5 8
delete 8

add 3
3 7 10 9 5
add 2
3 7 5 2
delete 6
2
delete 10
9
delete 7
9
add 1
3 1 9 2
delete 1
9
delete 3
9 2
delete 5

delete 2


output:

1 9
9
2 4 9
9
3 6 4 9
9
2 6 4
4
3 7 9 4
7
0
7
3 5 9 7
7
4 8 9 5 7
7
5 10 8 9 5 7
7
0
7
5 3 9 10 5 7
3
4 2 5 7 3
3
1 2
3
1 9
3
1 9
3
4 1 9 2 3
3
1 9
3
2 2 9
9
0 9
0 -1

result:

wrong answer WA in query 5 queried element 9 was not from S