QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32485#1458. Binary Search AlgorithmcdwWA 4ms3564kbC++201.6kb2022-05-20 18:52:522022-05-20 18:52:52

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-20 18:52:52]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3564kb
  • [2022-05-20 18:52:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1 << 13, M = N << 1;
int rk[N];
vector<int> vec;
void qry(){
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	cout << vec.size();
	for(int i : vec) cout << ' ' << i;
	cout << endl;
	for(int i = 0, x;i < vec.size();++ i){cin >> x; rk[x] = i;}
}
int n, seg[M];
char op[10];
void add1(int p){
	int x = 1, L = 1, R = n;
	vec.push_back(p);
	while(true){
		if(seg[x]) vec.push_back(seg[x]);
		if(L == R) return;
		int md = L + R >> 1; x <<= 1;
		p <= md ? R = md : L = md + 1, x |= 1;
	}
}
void add2(int p){
	int x = 1, L = 1, R = n;
	while(true){
		if(!seg[x] || rk[seg[x]] > rk[p]) seg[x] = p;
		if(L == R) return;
		int md = L + R >> 1; x <<= 1;
		p <= md ? R = md : L = md + 1, x |= 1;
	}
}
void del1(int p){
	int x = 1, L = 1, R = n;
	while(L < R){
		int md = L + R >> 1; x <<= 1;
		if(p <= md){
			if(seg[x | 1]) vec.push_back(seg[x | 1]);
			R = md;
		} else {
			if(seg[x]) vec.push_back(seg[x]);
			L = md + 1; x |= 1;
		}
	}
}
void del2(int p, int x = 1, int L = 1, int R = n){
	if(L == R){seg[x] = 0; return;}
	int md = L + R >> 1;
	p <= md ? del2(p, x << 1, L, md) : del2(p, x << 1 | 1, md + 1, R);
	seg[x] = seg[x << 1] && seg[x << 1 | 1] ? seg[x << 1 | (rk[seg[x << 1]] > rk[seg[x << 1 | 1]])] : (seg[x << 1] | seg[x << 1 | 1]);
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(int $ = 0, x;$ < (n << 1);++ $){
		cin >> op >> x; vec.clear();
		if(op[0] == 'a'){add1(x); qry(); add2(x);}
		else {vec.clear(); del1(x); qry(); del2(x);}
		cout << (seg[1] ?: -1) << endl;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 3564kb

input:

3
add 1
1
add 3
3 1
delete 1
3
add 2
3 1 2
delete 3

delete 2


output:

1 1
1
2 1 3
3
1 3
3
3 1 2 3
3
0
-1
0
-1

result:

wrong answer WA in query 4 queried element 1 was not from S