QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32485 | #1458. Binary Search Algorithm | cdw | WA | 4ms | 3564kb | C++20 | 1.6kb | 2022-05-20 18:52:52 | 2022-05-20 18:52:52 |
Judging History
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