QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #803795 | #1458. Binary Search Algorithm | peimuda | AC ✓ | 115ms | 3940kb | C++11 | 2.9kb | 2024-12-07 18:37:39 | 2024-12-07 18:37:40 |
Judging History
answer
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
int rt;
int ls[8003],rs[8003];
int fa[8003];
int md[8003];
int cv[8003];
void upd(int x)
{
if(ls[x]>=0&&rs[x]>=0)
{
md[x]=min(md[ls[x]],md[rs[x]])+1;
if(cv[ls[x]]>cv[rs[x]]) swap(ls[x],rs[x]);
}
else
{
md[x]=0;
if(rs[x]>=0) swap(ls[x],rs[x]);
}
if(ls[x]>=0) fa[ls[x]]=x;
if(rs[x]>=0) fa[rs[x]]=x;
}
void upm(int x)
{
if(x==-1) return;
if(ls[x]>=0&&rs[x]>=0) md[x]=min(md[ls[x]],md[rs[x]])+1;
else md[x]=0;
upm(fa[x]);
}
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin>>n;
rt=-1;
string tp;
int x;
n*=2;
int cs=0;
while(n--)
{
cin>>tp>>x;
x--;
if(tp=="add")
{
cs++;
ls[x]=-1;
rs[x]=-1;
if(rt==-1)
{
cout<<0<<endl;
cout.flush();
rt=x;
}
else
{
vector<int> v;
v.push_back(rt);
v.push_back(x);
vector<int> g;
int j;
for(j=rt;rs[j]!=-1;)
{
v.push_back(ls[j]);
v.push_back(rs[j]);
g.push_back(j);
if(md[ls[j]]<=md[rs[j]]) j=ls[j];
else j=rs[j];
}
if(ls[j]>=0) v.push_back(ls[j]);
g.push_back(j);
cout<<v.size();
for(int i:v) cout<<' '<<i+1;
cout<<endl;
cout.flush();
for(int i=0;i<v.size();i++)
{
int o;
cin>>o;
o--;
cv[o]=i;
}
rs[j]=x;
int i;
for(i=g.size()-1;i>=0;i--)
{
if(cv[g[i]]<cv[x]) break;
int s=g[i];
if(i>0)
{
if(ls[g[i-1]]==s) ls[g[i-1]]=x;
else rs[g[i-1]]=x;
}
else rt=x;
swap(ls[x],ls[s]);
swap(rs[x],rs[s]);
if(ls[x]==x) ls[x]=s;
else rs[x]=s;
upd(s);
}
upd(x);
for(;i>=0;i--) upd(g[i]);
}
fa[rt]=-1;
}
else
{
cs--;
if(cs==0)
{
cout<<0<<endl;
cout.flush();
rt=-1;
}
else
{
vector<int> v;
vector<int> g;
int j;
int rf=fa[x];
if(rf!=-1)
{
if(ls[rf]==x&&rs[rf]!=-1) v.push_back(rs[rf]);
if(rs[rf]==x&&ls[rf]!=-1) v.push_back(ls[rf]);
}
for(j=x;ls[j]!=-1;j=ls[j])
{
v.push_back(ls[j]);
if(rs[j]>=0) v.push_back(rs[j]);
g.push_back(ls[j]);
}
cout<<v.size();
for(int i:v) cout<<' '<<i+1;
cout<<endl;
cout.flush();
for(int i=0;i<v.size();i++)
{
int o;
cin>>o;
o--;
cv[o]=i;
}
for(int i=0;i<g.size();i++)
{
int s=g[i];
if(fa[x]!=-1)
{
if(ls[fa[x]]==x) ls[fa[x]]=s;
else rs[fa[x]]=s;
}
else rt=s;
fa[s]=fa[x];
fa[x]=s;
ls[x]=ls[s];
ls[s]=x;
swap(rs[x],rs[s]);
}
if(ls[fa[x]]==x) ls[fa[x]]=-1;
else rs[fa[x]]=-1;
for(int i=((int)g.size())-1;i>=0;i--) upd(g[i]);
if(rf>=0) upd(rf);
if(g.size()) upm(fa[g[0]]);
else upm(rf);
fa[rt]=-1;
}
}
if(rt==-1) cout<<"-1"<<endl;
else cout<<rt+1<<endl;
cout.flush();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
3 add 1 add 3 3 1 delete 1 add 2 3 2 delete 3 2 delete 2
output:
0 1 2 1 3 3 0 3 2 3 2 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
10 add 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 5 add 3 3 7 10 5 6 add 2 3 7 6 2 delete 6 7 2 delete 10 5 delete 7 5 2 add 1 3 1 5 2 delete 1 5 2 delete 3 5 2 delete 5 2 delete 2
output:
0 9 2 9 4 9 3 9 6 4 9 2 4 6 4 3 4 7 6 7 1 6 7 3 7 5 6 7 4 7 8 5 6 7 5 7 10 5 6 8 7 1 5 7 5 7 3 10 6 5 3 4 3 2 7 6 3 2 7 2 3 1 5 3 2 2 5 3 4 3 1 5 2 3 2 2 5 3 2 5 2 5 1 2 2 0 -1
result:
ok n=10, OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
100 add 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 59 96 add 50 81 50 94 59 96 add 57 81 50 57 94 59 96 add 39 39 81 50 57 94 59 96 add 55 39 81 50 94 55 96 add 23 39 81 50 94 23 55 96 add 40 39 81 40 94 32 35 add 5 39 81 40 94 32 35 5 add 2 39 81 40 94 35...
output:
0 81 2 81 96 81 3 81 94 96 81 4 81 32 94 96 81 5 81 35 94 96 32 81 4 81 59 94 96 81 5 81 50 94 59 96 81 6 81 57 50 94 59 96 81 7 81 39 50 94 57 96 59 39 6 39 55 81 94 50 96 39 7 39 23 81 94 50 55 96 39 6 39 40 81 94 32 35 39 7 39 5 81 40 94 35 32 39 6 39 2 81 40 94 35 39 1 96 39 7 39 12 81 40 50 23 ...
result:
ok n=100, OK
Test #4:
score: 0
Accepted
time: 3ms
memory: 3636kb
input:
100 add 71 add 75 71 75 add 43 43 71 75 add 69 43 71 69 75 add 55 43 71 69 55 75 add 89 43 71 89 75 add 31 43 71 89 31 75 add 52 43 71 89 69 55 52 add 24 24 43 71 89 69 55 52 add 6 24 43 71 89 6 55 add 9 24 43 71 89 6 55 9 add 62 24 43 89 62 31 75 add 19 24 43 89 62 31 75 19 add 35 24 43 35 89 62 7...
output:
0 71 2 71 75 71 3 71 43 75 43 4 43 69 71 75 43 5 43 55 71 75 69 43 4 43 89 71 75 43 5 43 31 71 89 75 43 6 43 52 71 89 69 55 43 7 43 24 71 89 69 55 52 24 6 24 6 43 89 71 55 24 7 24 9 43 89 71 6 55 24 6 24 62 43 89 31 75 24 7 24 19 43 89 62 75 31 24 6 24 35 43 89 62 75 24 7 24 38 43 35 89 62 75 24 8 2...
result:
ok n=100, OK
Test #5:
score: 0
Accepted
time: 13ms
memory: 3512kb
input:
1000 add 93 add 917 93 917 add 921 93 917 921 add 70 93 917 921 70 add 949 93 949 917 921 70 add 777 93 949 777 921 add 237 93 949 777 237 921 add 581 581 93 949 777 917 70 add 461 581 93 949 777 917 70 461 add 319 581 93 949 777 319 70 add 42 581 93 949 777 42 319 70 add 690 581 93 690 777 237 921...
output:
0 93 2 93 917 93 3 93 921 917 93 4 93 70 917 921 93 5 93 949 917 921 70 93 4 93 777 949 921 93 5 93 237 949 777 921 93 6 93 581 949 777 917 70 581 7 581 461 93 777 949 70 917 581 6 581 319 93 777 949 70 581 7 581 42 93 777 949 319 70 581 6 581 690 93 777 237 921 581 7 581 631 93 690 777 921 237 581 ...
result:
ok n=1000, OK
Test #6:
score: 0
Accepted
time: 6ms
memory: 3644kb
input:
1000 add 589 add 844 589 844 add 341 589 341 844 add 362 589 341 844 362 add 955 955 589 341 844 362 add 565 955 589 565 844 add 467 955 589 565 844 467 add 664 955 589 565 341 664 362 add 167 167 955 589 565 341 664 362 add 879 167 955 589 565 362 879 add 934 167 934 955 589 565 362 879 add 757 16...
output:
0 589 2 589 844 589 3 589 341 844 589 4 589 362 341 844 589 5 589 955 341 844 362 955 4 955 565 589 844 955 5 955 467 589 565 844 955 6 955 664 589 565 341 362 955 7 955 167 589 565 341 362 664 167 6 167 879 955 565 589 362 167 7 167 934 955 565 589 362 879 167 6 167 757 934 565 844 467 167 7 167 94...
result:
ok n=1000, OK
Test #7:
score: 0
Accepted
time: 70ms
memory: 3716kb
input:
8000 add 2497 add 827 827 2497 add 4801 827 4801 2497 add 2709 827 4801 2709 2497 add 4516 827 4801 2709 4516 2497 add 656 827 656 4801 2497 add 4773 4773 827 656 4801 2497 add 1444 4773 827 656 4801 1444 2497 add 2338 4773 827 656 4801 1444 2338 2497 add 1254 4773 827 656 4801 1254 2497 add 5749 4...
output:
0 2497 2 2497 827 827 3 827 4801 2497 827 4 827 2709 4801 2497 827 5 827 4516 4801 2497 2709 827 4 827 656 4801 2497 827 5 827 4773 656 4801 2497 4773 6 4773 1444 827 4801 656 2497 4773 7 4773 2338 827 4801 656 2497 1444 4773 6 4773 1254 827 4801 656 2497 4773 7 4773 5749 827 4801 656 1254 2497 4773...
result:
ok n=8000, OK
Test #8:
score: 0
Accepted
time: 88ms
memory: 3892kb
input:
8000 add 1866 add 5228 5228 1866 add 4496 5228 4496 1866 add 2574 5228 4496 1866 2574 add 1492 5228 4496 1866 2574 1492 add 5427 5228 4496 1866 5427 add 3355 3355 5228 4496 1866 5427 add 5495 3355 5228 4496 1866 5495 5427 add 6421 3355 5228 4496 1866 5495 6421 5427 add 7543 3355 7543 5228 4496 1866...
output:
0 1866 2 1866 5228 5228 3 5228 4496 1866 5228 4 5228 2574 4496 1866 5228 5 5228 1492 4496 1866 2574 5228 4 5228 5427 4496 1866 5228 5 5228 3355 4496 1866 5427 3355 6 3355 5495 5228 4496 1866 5427 3355 7 3355 6421 5228 4496 1866 5427 5495 3355 6 3355 7543 5228 4496 1866 5427 3355 7 3355 4400 7543 449...
result:
ok n=8000, OK
Test #9:
score: 0
Accepted
time: 19ms
memory: 3768kb
input:
1000 add 964 add 650 964 650 add 967 964 650 967 add 129 964 650 967 129 add 345 964 650 967 129 345 add 454 964 650 967 454 add 614 964 650 967 454 614 add 11 964 650 967 129 345 11 add 963 964 650 967 129 345 11 963 add 357 964 650 967 129 345 357 add 300 964 650 967 129 345 357 300 add 785 964 6...
output:
0 964 2 964 650 964 3 964 967 650 964 4 964 129 650 967 964 5 964 345 650 967 129 964 4 964 454 650 967 964 5 964 614 650 967 454 964 6 964 11 650 967 129 345 964 7 964 963 650 967 129 345 11 964 6 964 357 650 967 129 345 964 7 964 300 650 967 129 345 357 964 6 964 785 650 967 454 614 964 7 964 700 ...
result:
ok n=1000, OK
Test #10:
score: 0
Accepted
time: 5ms
memory: 3540kb
input:
1000 add 651 add 792 792 651 add 816 792 816 651 add 325 792 816 651 325 add 876 792 816 651 325 876 add 408 792 816 651 408 add 289 792 816 289 651 408 add 746 792 746 816 289 325 876 add 492 792 746 816 289 325 876 492 add 2 792 746 816 289 2 876 add 462 792 746 462 816 289 2 876 add 98 792 746 2...
output:
0 651 2 651 792 792 3 792 816 651 792 4 792 325 816 651 792 5 792 876 816 651 325 792 4 792 408 816 651 792 5 792 289 816 651 408 792 6 792 746 816 289 325 876 792 7 792 492 746 289 816 876 325 792 6 792 2 746 289 816 876 792 7 792 462 746 289 816 2 876 792 6 792 98 746 289 651 408 792 7 792 68 746 ...
result:
ok n=1000, OK
Test #11:
score: 0
Accepted
time: 86ms
memory: 3744kb
input:
8000 add 4964 add 650 4964 650 add 6871 4964 650 6871 add 129 4964 650 6871 129 add 3768 4964 650 6871 129 3768 add 1551 4964 650 6871 1551 add 6223 4964 650 6871 1551 6223 add 3875 4964 650 6871 129 3768 3875 add 6536 4964 650 6871 129 3768 3875 6536 add 6438 4964 650 6871 129 3768 6438 add 5015 4...
output:
0 4964 2 4964 650 4964 3 4964 6871 650 4964 4 4964 129 650 6871 4964 5 4964 3768 650 6871 129 4964 4 4964 1551 650 6871 4964 5 4964 6223 650 6871 1551 4964 6 4964 3875 650 6871 129 3768 4964 7 4964 6536 650 6871 129 3768 3875 4964 6 4964 6438 650 6871 129 3768 4964 7 4964 5015 650 6871 129 3768 6438...
result:
ok n=8000, OK
Test #12:
score: 0
Accepted
time: 87ms
memory: 3652kb
input:
8000 add 3562 add 2628 3562 2628 add 6508 6508 3562 2628 add 1830 6508 3562 2628 1830 add 6995 6508 6995 3562 2628 1830 add 2741 6508 6995 2741 2628 add 3523 6508 6995 2741 3523 2628 add 4497 6508 6995 4497 2741 3562 1830 add 1175 6508 6995 4497 2741 3562 1175 1830 add 5626 6508 6995 4497 2741 5626...
output:
0 3562 2 3562 2628 3562 3 3562 6508 2628 6508 4 6508 1830 3562 2628 6508 5 6508 6995 3562 2628 1830 6508 4 6508 2741 6995 2628 6508 5 6508 3523 6995 2741 2628 6508 6 6508 4497 6995 2741 3562 1830 6508 7 6508 1175 6995 2741 4497 1830 3562 6508 6 6508 5626 6995 2741 4497 1830 6508 7 6508 2252 6995 274...
result:
ok n=8000, OK
Test #13:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
10 add 3 add 7 3 7 add 10 3 7 10 add 1 3 7 10 1 add 9 3 7 10 1 9 add 5 3 7 10 5 add 4 3 7 10 5 4 add 8 3 7 10 1 9 8 add 6 3 7 10 1 9 8 6 add 2 3 7 10 1 9 2 delete 3 7 10 1 9 8 6 delete 7 10 1 5 4 delete 10 1 9 5 8 2 delete 1 9 5 8 6 2 delete 9 5 4 8 delete 5 4 8 delete 8 6 2 delete 4 6 2 delete 6 2...
output:
0 3 2 3 7 3 3 3 10 7 3 4 3 1 7 10 3 5 3 9 7 10 1 3 4 3 5 7 10 3 5 3 4 7 10 5 3 6 3 8 7 10 1 9 3 7 3 6 7 10 1 9 8 3 6 3 2 7 10 1 9 3 6 7 10 1 9 8 6 7 4 10 1 5 4 10 5 1 5 9 8 2 1 5 9 5 8 2 6 9 3 5 8 4 5 2 4 8 4 2 6 2 4 2 6 2 6 1 2 2 0 -1
result:
ok n=10, OK
Test #14:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
10 add 9 add 5 9 5 add 2 9 5 2 add 7 7 9 5 2 add 4 7 9 5 4 2 add 3 3 7 9 2 add 1 3 7 1 9 2 add 6 3 7 1 9 6 2 add 10 3 7 10 1 9 6 2 add 8 3 7 10 9 8 2 delete 9 7 5 4 delete 7 10 1 5 8 6 delete 2 delete 5 10 4 delete 3 10 1 4 8 6 delete 10 1 4 8 6 delete 1 4 8 delete 4 8 6 delete 8 6 delete 6
output:
0 9 2 9 5 9 3 9 2 5 9 4 9 7 5 2 7 5 7 4 9 2 5 7 4 7 3 9 2 3 5 3 1 7 9 2 3 6 3 6 7 9 1 2 3 7 3 10 7 9 1 2 6 3 6 3 8 7 9 10 2 3 3 7 5 4 3 5 5 10 8 1 6 3 0 3 2 10 4 3 5 10 4 1 8 6 10 4 1 4 8 6 1 2 4 8 4 2 8 6 8 1 6 6 0 -1
result:
ok n=10, OK
Test #15:
score: 0
Accepted
time: 31ms
memory: 3584kb
input:
1000 add 964 add 650 964 650 add 967 964 650 967 add 129 964 650 967 129 add 345 964 650 967 129 345 add 454 964 650 967 454 add 614 964 650 967 454 614 add 11 964 650 967 129 345 11 add 963 964 650 967 129 345 11 963 add 357 964 650 967 129 345 357 add 300 964 650 967 129 345 357 300 add 785 964 6...
output:
0 964 2 964 650 964 3 964 967 650 964 4 964 129 650 967 964 5 964 345 650 967 129 964 4 964 454 650 967 964 5 964 614 650 967 454 964 6 964 11 650 967 129 345 964 7 964 963 650 967 129 345 11 964 6 964 357 650 967 129 345 964 7 964 300 650 967 129 345 357 964 6 964 785 650 967 454 614 964 7 964 700 ...
result:
ok n=1000, OK
Test #16:
score: 0
Accepted
time: 11ms
memory: 3596kb
input:
1000 add 871 add 449 449 871 add 644 644 449 871 add 97 97 644 449 871 add 853 853 97 644 449 871 add 496 496 853 97 871 add 418 418 496 853 97 871 add 207 207 418 496 853 97 871 add 401 401 207 418 496 853 97 871 add 519 519 401 207 418 97 871 add 276 276 519 401 207 418 97 871 add 576 576 276 519...
output:
0 871 2 871 449 449 3 449 644 871 644 4 644 97 449 871 97 5 97 853 644 871 449 853 4 853 496 97 871 496 5 496 418 853 97 871 418 6 418 207 496 97 853 871 207 7 207 401 418 97 496 871 853 401 6 401 519 207 97 418 871 519 7 519 276 401 97 207 418 871 276 6 276 576 519 97 644 449 576 7 576 74 276 519 9...
result:
ok n=1000, OK
Test #17:
score: 0
Accepted
time: 4ms
memory: 3816kb
input:
1000 add 35 add 747 35 747 add 391 35 391 747 add 770 35 391 770 747 add 707 35 391 770 747 707 add 344 35 391 747 344 add 881 35 391 747 881 344 add 753 35 391 770 747 707 753 add 266 35 391 770 747 707 753 266 add 126 126 35 391 770 747 707 add 11 11 126 35 391 770 747 707 add 705 11 126 747 881 ...
output:
0 35 2 35 747 35 3 35 391 747 35 4 35 770 391 747 35 5 35 707 391 747 770 35 4 35 344 391 747 35 5 35 881 391 747 344 35 6 35 753 391 747 770 707 35 7 35 266 391 747 770 707 753 35 6 35 126 391 747 770 707 126 7 126 11 35 747 391 770 707 11 6 11 705 126 747 881 344 11 7 11 672 126 747 881 344 705 11...
result:
ok n=1000, OK
Test #18:
score: 0
Accepted
time: 18ms
memory: 3628kb
input:
1000 add 914 add 326 326 914 add 650 650 326 914 add 629 650 629 326 914 add 626 650 626 629 326 914 add 416 650 626 416 914 add 785 650 785 626 416 914 add 837 650 785 837 626 416 914 add 300 650 300 785 837 626 416 914 add 700 650 300 785 700 626 914 add 164 650 300 785 700 164 626 914 add 786 65...
output:
0 914 2 914 326 326 3 326 650 914 650 4 650 629 326 914 650 5 650 626 629 914 326 650 4 650 416 626 914 650 5 650 785 626 416 914 650 6 650 837 785 626 416 914 650 7 650 300 785 626 837 914 416 650 6 650 700 300 626 785 914 650 7 650 164 300 626 785 700 914 650 6 650 786 300 626 629 326 650 7 650 30...
result:
ok n=1000, OK
Test #19:
score: 0
Accepted
time: 3ms
memory: 3540kb
input:
1000 add 129 add 786 129 786 add 614 129 614 786 add 967 967 129 614 786 add 454 967 129 454 614 786 add 34 967 129 34 786 add 700 967 129 700 34 786 add 300 967 129 454 614 300 700 add 488 967 129 454 614 300 700 488 add 963 967 129 454 614 963 700 add 79 967 129 454 614 963 700 79 add 743 967 129...
output:
0 129 2 129 786 129 3 129 614 786 129 4 129 967 614 786 967 5 967 454 129 786 614 967 4 967 34 129 786 967 5 967 700 129 34 786 967 6 967 300 129 700 454 614 967 7 967 488 129 700 454 614 300 967 6 967 963 129 700 454 614 967 7 967 79 129 700 454 614 963 967 6 967 743 129 700 34 786 967 7 967 11 129...
result:
ok n=1000, OK
Test #20:
score: 0
Accepted
time: 89ms
memory: 3940kb
input:
8000 add 4964 add 650 4964 650 add 6871 4964 650 6871 add 129 4964 650 6871 129 add 3768 4964 650 6871 129 3768 add 1551 4964 650 6871 1551 add 6223 4964 650 6871 1551 6223 add 3875 4964 650 6871 129 3768 3875 add 6536 4964 650 6871 129 3768 3875 6536 add 6438 4964 650 6871 129 3768 6438 add 5015 4...
output:
0 4964 2 4964 650 4964 3 4964 6871 650 4964 4 4964 129 650 6871 4964 5 4964 3768 650 6871 129 4964 4 4964 1551 650 6871 4964 5 4964 6223 650 6871 1551 4964 6 4964 3875 650 6871 129 3768 4964 7 4964 6536 650 6871 129 3768 3875 4964 6 4964 6438 650 6871 129 3768 4964 7 4964 5015 650 6871 129 3768 6438...
result:
ok n=8000, OK
Test #21:
score: 0
Accepted
time: 89ms
memory: 3936kb
input:
8000 add 3493 add 5110 5110 3493 add 533 533 5110 3493 add 1700 1700 533 5110 3493 add 4277 4277 1700 533 5110 3493 add 2368 2368 4277 1700 3493 add 4495 4495 2368 4277 1700 3493 add 4305 4305 4495 2368 4277 1700 3493 add 6965 6965 4305 4495 2368 4277 1700 3493 add 2503 2503 6965 4305 4495 1700 349...
output:
0 3493 2 3493 5110 5110 3 5110 533 3493 533 4 533 1700 5110 3493 1700 5 1700 4277 533 3493 5110 4277 4 4277 2368 1700 3493 2368 5 2368 4495 4277 1700 3493 4495 6 4495 4305 2368 1700 4277 3493 4305 7 4305 6965 4495 1700 2368 3493 4277 6965 6 6965 2503 4305 1700 4495 3493 2503 7 2503 4339 6965 1700 43...
result:
ok n=8000, OK
Test #22:
score: 0
Accepted
time: 115ms
memory: 3724kb
input:
8000 add 612 add 2743 612 2743 add 7916 612 2743 7916 add 1433 1433 612 2743 7916 add 2140 1433 612 2140 2743 7916 add 840 1433 612 7916 840 add 4289 1433 612 4289 7916 840 add 3912 1433 612 4289 2140 3912 2743 add 6323 1433 612 4289 2140 3912 2743 6323 add 3859 1433 612 4289 3859 2140 2743 add 436...
output:
0 612 2 612 2743 612 3 612 7916 2743 612 4 612 1433 2743 7916 1433 5 1433 2140 612 7916 2743 1433 4 1433 840 612 7916 1433 5 1433 4289 612 7916 840 1433 6 1433 3912 612 4289 2140 2743 1433 7 1433 6323 612 4289 2140 2743 3912 1433 6 1433 3859 612 4289 2140 2743 1433 7 1433 4368 612 4289 3859 2140 274...
result:
ok n=8000, OK
Test #23:
score: 0
Accepted
time: 75ms
memory: 3696kb
input:
8000 add 3393 add 5029 5029 3393 add 650 650 5029 3393 add 3599 650 5029 3393 3599 add 5102 650 5102 5029 3393 3599 add 5122 650 5102 3393 5122 add 6641 650 5102 6641 3393 5122 add 475 650 5102 5029 6641 475 3599 add 1323 650 5102 5029 6641 475 3599 1323 add 1821 650 5102 1821 5029 6641 3599 add 34...
output:
0 3393 2 3393 5029 5029 3 5029 650 3393 650 4 650 3599 5029 3393 650 5 650 5102 5029 3393 3599 650 4 650 5122 5102 3393 650 5 650 6641 5102 3393 5122 650 6 650 475 5102 6641 5029 3599 650 7 650 1323 5102 6641 5029 3599 475 650 6 650 1821 5102 6641 5029 3599 650 7 650 3447 5102 6641 1821 5029 3599 65...
result:
ok n=8000, OK
Test #24:
score: 0
Accepted
time: 109ms
memory: 3748kb
input:
8000 add 3768 add 878 3768 878 add 5029 3768 5029 878 add 1821 3768 1821 5029 878 add 5001 3768 1821 5029 5001 878 add 1608 3768 1821 1608 878 add 2691 3768 1821 1608 878 2691 add 7293 3768 1821 5029 5001 1608 7293 add 7275 3768 1821 5029 5001 7275 1608 7293 add 6223 3768 6223 1821 5029 5001 1608 a...
output:
0 3768 2 3768 878 3768 3 3768 5029 878 3768 4 3768 1821 5029 878 3768 5 3768 5001 1821 878 5029 3768 4 3768 1608 1821 878 3768 5 3768 2691 1821 1608 878 3768 6 3768 7293 1821 1608 5029 5001 3768 7 3768 7275 1821 1608 5029 5001 7293 3768 6 3768 6223 1821 1608 5029 5001 3768 7 3768 227 6223 1608 1821 ...
result:
ok n=8000, OK
Test #25:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10 add 3 add 7 3 7 add 10 3 7 10 add 1 3 7 10 1 add 9 3 7 10 1 9 add 5 3 7 10 5 add 4 3 7 10 5 4 add 8 3 7 10 1 9 8 add 6 3 7 10 1 9 8 6 add 2 3 7 10 1 9 2 delete 3 7 10 1 9 8 6 delete 7 10 1 5 4 delete 10 1 9 5 8 2 delete 1 9 5 8 6 2 delete 9 5 4 8 delete 5 4 8 delete 8 6 2 delete 6 2 delete 4 2 d...
output:
0 3 2 3 7 3 3 3 10 7 3 4 3 1 7 10 3 5 3 9 7 10 1 3 4 3 5 7 10 3 5 3 4 7 10 5 3 6 3 8 7 10 1 9 3 7 3 6 7 10 1 9 8 3 6 3 2 7 10 1 9 3 6 7 10 1 9 8 6 7 4 10 1 5 4 10 5 1 5 9 8 2 1 5 9 5 8 2 6 9 3 5 8 4 5 2 4 8 4 2 6 2 4 1 2 4 1 2 2 0 -1
result:
ok n=10, OK
Test #26:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
10 add 10 add 8 10 8 add 4 10 4 8 add 3 3 10 4 8 add 6 3 10 4 8 6 add 1 3 10 1 8 add 7 3 7 10 1 8 add 2 3 7 10 1 8 2 add 9 3 7 10 1 9 8 2 add 5 3 7 10 1 5 8 delete 10 7 4 6 delete 8 delete 3 7 1 9 5 4 2 delete 7 1 9 5 4 2 delete 1 9 5 4 2 delete 4 5 6 delete 9 5 6 2 delete 5 6 2 delete 6 2 delete 2
output:
0 10 2 10 8 10 3 10 4 8 10 4 10 3 4 8 3 5 3 6 10 8 4 3 4 3 1 10 8 3 5 3 7 10 1 8 3 6 3 2 7 10 1 8 3 7 3 9 7 10 1 8 2 3 6 3 5 7 10 1 8 3 3 7 4 6 3 0 3 6 7 4 1 5 9 2 7 5 1 4 9 5 2 1 4 9 4 5 2 9 2 5 6 9 3 5 6 2 5 2 6 2 6 1 2 2 0 -1
result:
ok n=10, OK
Test #27:
score: 0
Accepted
time: 12ms
memory: 3528kb
input:
1000 add 964 add 650 964 650 add 967 964 650 967 add 129 964 650 967 129 add 345 964 650 967 129 345 add 454 964 650 967 454 add 614 964 650 967 454 614 add 11 964 650 967 129 345 11 add 963 964 650 967 129 345 11 963 add 357 964 650 967 129 345 357 add 300 964 650 967 129 345 357 300 add 785 964 6...
output:
0 964 2 964 650 964 3 964 967 650 964 4 964 129 650 967 964 5 964 345 650 967 129 964 4 964 454 650 967 964 5 964 614 650 967 454 964 6 964 11 650 967 129 345 964 7 964 963 650 967 129 345 11 964 6 964 357 650 967 129 345 964 7 964 300 650 967 129 345 357 964 6 964 785 650 967 454 614 964 7 964 700 ...
result:
ok n=1000, OK
Test #28:
score: 0
Accepted
time: 4ms
memory: 3584kb
input:
1000 add 871 add 449 449 871 add 644 644 449 871 add 97 97 644 449 871 add 853 853 97 644 449 871 add 496 496 853 97 871 add 418 418 496 853 97 871 add 207 207 418 496 853 97 871 add 401 401 207 418 496 853 97 871 add 519 519 401 207 418 97 871 add 276 276 519 401 207 418 97 871 add 576 576 276 519...
output:
0 871 2 871 449 449 3 449 644 871 644 4 644 97 449 871 97 5 97 853 644 871 449 853 4 853 496 97 871 496 5 496 418 853 97 871 418 6 418 207 496 97 853 871 207 7 207 401 418 97 496 871 853 401 6 401 519 207 97 418 871 519 7 519 276 401 97 207 418 871 276 6 276 576 519 97 644 449 576 7 576 74 276 519 9...
result:
ok n=1000, OK
Test #29:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1000 add 986 add 800 986 800 add 897 986 800 897 add 601 601 986 800 897 add 858 858 601 986 800 897 add 627 858 601 627 897 add 398 858 601 627 398 897 add 124 858 124 601 986 627 800 add 885 858 124 885 601 986 627 800 add 554 858 124 885 554 627 800 add 234 858 124 885 554 234 627 800 add 482 85...
output:
0 986 2 986 800 986 3 986 897 800 986 4 986 601 800 897 601 5 601 858 986 897 800 858 4 858 627 601 897 858 5 858 398 601 627 897 858 6 858 124 601 627 986 800 858 7 858 885 124 627 601 800 986 858 6 858 554 124 627 885 800 858 7 858 234 124 627 885 554 800 858 6 858 482 124 627 398 897 858 7 858 48...
result:
ok n=1000, OK
Test #30:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1000 add 101 add 442 442 101 add 183 442 101 183 add 373 442 101 373 183 add 837 442 101 837 373 183 add 326 442 101 183 326 add 585 442 101 585 183 326 add 450 442 101 585 450 837 373 add 15 442 101 585 15 450 837 373 add 626 442 101 585 15 626 373 add 914 442 101 585 15 626 373 914 add 786 442 10...
output:
0 101 2 101 442 442 3 442 183 101 442 4 442 373 101 183 442 5 442 837 101 183 373 442 4 442 326 101 183 442 5 442 585 101 183 326 442 6 442 450 101 585 837 373 442 7 442 15 101 585 450 373 837 442 6 442 626 101 585 15 373 442 7 442 914 101 585 15 626 373 442 6 442 786 101 585 183 326 442 7 442 494 1...
result:
ok n=1000, OK
Test #31:
score: 0
Accepted
time: 14ms
memory: 3632kb
input:
1000 add 79 add 442 442 79 add 454 454 442 79 add 520 454 442 79 520 add 101 454 442 79 101 520 add 343 454 442 79 343 add 585 454 442 79 343 585 add 700 454 700 442 79 101 520 add 632 454 700 442 79 101 632 520 add 300 454 300 700 442 79 520 add 878 454 300 700 442 79 878 520 add 64 454 300 79 343...
output:
0 79 2 79 442 442 3 442 454 79 454 4 454 520 442 79 454 5 454 101 442 79 520 454 4 454 343 442 79 454 5 454 585 442 79 343 454 6 454 700 442 79 101 520 454 7 454 632 700 79 442 520 101 454 6 454 300 700 79 442 520 454 7 454 878 300 79 700 442 520 454 6 454 64 300 79 343 585 454 7 454 227 300 79 343 ...
result:
ok n=1000, OK
Test #32:
score: 0
Accepted
time: 3ms
memory: 3596kb
input:
1000 add 964 add 871 964 871 add 449 964 449 871 add 644 964 644 449 871 add 97 964 97 644 449 871 add 853 964 853 97 871 add 496 964 496 853 97 871 add 418 964 418 496 853 97 871 add 207 964 207 418 496 853 97 871 add 401 964 401 207 418 97 871 add 519 964 519 401 207 418 97 871 add 276 964 276 51...
output:
0 964 2 964 871 964 3 964 449 871 964 4 964 644 449 871 964 5 964 97 644 871 449 964 4 964 853 97 871 964 5 964 496 853 97 871 964 6 964 418 496 97 853 871 964 7 964 207 418 97 496 871 853 964 6 964 401 207 97 418 871 964 7 964 519 401 97 207 418 871 964 6 964 276 519 97 644 449 964 7 964 576 276 51...
result:
ok n=1000, OK
Test #33:
score: 0
Accepted
time: 83ms
memory: 3652kb
input:
8000 add 4964 add 650 4964 650 add 6871 4964 650 6871 add 129 4964 650 6871 129 add 3768 4964 650 6871 129 3768 add 1551 4964 650 6871 1551 add 6223 4964 650 6871 1551 6223 add 3875 4964 650 6871 129 3768 3875 add 6536 4964 650 6871 129 3768 3875 6536 add 6438 4964 650 6871 129 3768 6438 add 5015 4...
output:
0 4964 2 4964 650 4964 3 4964 6871 650 4964 4 4964 129 650 6871 4964 5 4964 3768 650 6871 129 4964 4 4964 1551 650 6871 4964 5 4964 6223 650 6871 1551 4964 6 4964 3875 650 6871 129 3768 4964 7 4964 6536 650 6871 129 3768 3875 4964 6 4964 6438 650 6871 129 3768 4964 7 4964 5015 650 6871 129 3768 6438...
result:
ok n=8000, OK
Test #34:
score: 0
Accepted
time: 93ms
memory: 3768kb
input:
8000 add 3493 add 5110 5110 3493 add 533 533 5110 3493 add 1700 1700 533 5110 3493 add 4277 4277 1700 533 5110 3493 add 2368 2368 4277 1700 3493 add 4495 4495 2368 4277 1700 3493 add 4305 4305 4495 2368 4277 1700 3493 add 6965 6965 4305 4495 2368 4277 1700 3493 add 2503 2503 6965 4305 4495 1700 349...
output:
0 3493 2 3493 5110 5110 3 5110 533 3493 533 4 533 1700 5110 3493 1700 5 1700 4277 533 3493 5110 4277 4 4277 2368 1700 3493 2368 5 2368 4495 4277 1700 3493 4495 6 4495 4305 2368 1700 4277 3493 4305 7 4305 6965 4495 1700 2368 3493 4277 6965 6 6965 2503 4305 1700 4495 3493 2503 7 2503 4339 6965 1700 43...
result:
ok n=8000, OK
Test #35:
score: 0
Accepted
time: 74ms
memory: 3744kb
input:
8000 add 1338 add 1220 1338 1220 add 2046 1338 2046 1220 add 5158 5158 1338 2046 1220 add 1439 5158 1338 2046 1439 1220 add 412 5158 1338 412 1220 add 5737 5737 5158 1338 412 1220 add 3968 5737 5158 1338 412 3968 1220 add 703 5737 5158 1338 703 412 3968 1220 add 2858 5737 5158 2858 1338 703 1220 ad...
output:
0 1338 2 1338 1220 1338 3 1338 2046 1220 1338 4 1338 5158 2046 1220 5158 5 5158 1439 1338 1220 2046 5158 4 5158 412 1338 1220 5158 5 5158 5737 1338 412 1220 5737 6 5737 3968 5158 1338 412 1220 5737 7 5737 703 5158 1338 412 1220 3968 5737 6 5737 2858 5158 1338 703 1220 5737 7 5737 2783 5158 1338 2858...
result:
ok n=8000, OK
Test #36:
score: 0
Accepted
time: 74ms
memory: 3704kb
input:
8000 add 6131 add 4520 6131 4520 add 6799 6131 4520 6799 add 1676 6131 4520 1676 6799 add 1844 6131 4520 1676 1844 6799 add 6912 6131 4520 6912 6799 add 3621 6131 4520 6912 3621 6799 add 4018 4018 6131 4520 6912 1676 1844 add 1178 4018 1178 6131 4520 6912 1676 1844 add 2082 4018 1178 6131 6912 1844...
output:
0 6131 2 6131 4520 6131 3 6131 6799 4520 6131 4 6131 1676 4520 6799 6131 5 6131 1844 4520 6799 1676 6131 4 6131 6912 4520 6799 6131 5 6131 3621 4520 6912 6799 6131 6 6131 4018 4520 6912 1676 1844 4018 7 4018 1178 6131 6912 4520 1844 1676 4018 6 4018 2082 1178 6912 6131 1844 4018 7 4018 6172 1178 691...
result:
ok n=8000, OK
Test #37:
score: 0
Accepted
time: 62ms
memory: 3936kb
input:
8000 add 893 add 2960 2960 893 add 7459 7459 2960 893 add 111 111 7459 2960 893 add 1185 111 7459 1185 2960 893 add 3327 111 7459 3327 893 add 5397 5397 111 7459 3327 893 add 3963 5397 111 7459 3327 893 3963 add 4988 5397 111 7459 3327 893 3963 4988 add 6640 5397 111 7459 3327 6640 893 add 3584 539...
output:
0 893 2 893 2960 2960 3 2960 7459 893 7459 4 7459 111 2960 893 111 5 111 1185 7459 893 2960 111 4 111 3327 7459 893 111 5 111 5397 7459 3327 893 5397 6 5397 3963 111 7459 3327 893 5397 7 5397 4988 111 7459 3327 893 3963 5397 6 5397 6640 111 7459 3327 893 5397 7 5397 3584 111 7459 3327 6640 893 5397 ...
result:
ok n=8000, OK
Test #38:
score: 0
Accepted
time: 101ms
memory: 3796kb
input:
8000 add 3768 add 355 3768 355 add 5755 3768 5755 355 add 5029 3768 5029 5755 355 add 5530 3768 5029 5755 5530 355 add 7826 3768 5029 7826 355 add 6194 3768 5029 6194 7826 355 add 1821 3768 1821 5029 5755 6194 5530 add 1113 3768 1821 5029 5755 6194 5530 1113 add 5015 3768 5015 1821 5029 6194 5530 a...
output:
0 3768 2 3768 355 3768 3 3768 5755 355 3768 4 3768 5029 5755 355 3768 5 3768 5530 5029 355 5755 3768 4 3768 7826 5029 355 3768 5 3768 6194 5029 7826 355 3768 6 3768 1821 5029 6194 5755 5530 3768 7 3768 1113 1821 6194 5029 5530 5755 3768 6 3768 5015 1821 6194 5029 5530 3768 7 3768 343 5015 6194 1821 ...
result:
ok n=8000, OK
Test #39:
score: 0
Accepted
time: 51ms
memory: 3896kb
input:
8000 add 3325 add 5911 3325 5911 add 664 3325 5911 664 add 708 3325 5911 708 664 add 3589 3325 5911 3589 708 664 add 3869 3325 3869 5911 664 add 6353 3325 6353 3869 5911 664 add 5408 3325 6353 3869 5408 5911 664 add 2396 3325 6353 3869 5408 5911 664 2396 add 1926 3325 6353 3869 1926 5911 664 add 38...
output:
0 3325 2 3325 5911 3325 3 3325 664 5911 3325 4 3325 708 5911 664 3325 5 3325 3589 5911 664 708 3325 4 3325 3869 5911 664 3325 5 3325 6353 3869 5911 664 3325 6 3325 5408 6353 5911 3869 664 3325 7 3325 2396 6353 5911 3869 664 5408 3325 6 3325 1926 6353 5911 3869 664 3325 7 3325 3822 6353 5911 3869 192...
result:
ok n=8000, OK
Test #40:
score: 0
Accepted
time: 107ms
memory: 3648kb
input:
8000 add 520 add 4857 4857 520 add 3380 4857 520 3380 add 5397 4857 520 5397 3380 add 1551 1551 4857 520 5397 3380 add 4675 1551 4857 4675 3380 add 5755 1551 4857 4675 5755 3380 add 2691 1551 4857 4675 520 5397 2691 add 3809 1551 3809 4857 4675 520 5397 2691 add 1608 1551 3809 4857 4675 1608 5397 a...
output:
0 520 2 520 4857 4857 3 4857 3380 520 4857 4 4857 5397 520 3380 4857 5 4857 1551 520 3380 5397 1551 4 1551 4675 4857 3380 1551 5 1551 5755 4857 4675 3380 1551 6 1551 2691 4857 4675 520 5397 1551 7 1551 3809 4857 4675 520 5397 2691 1551 6 1551 1608 3809 4675 4857 5397 1551 7 1551 4679 3809 4675 4857 ...
result:
ok n=8000, OK
Test #41:
score: 0
Accepted
time: 76ms
memory: 3528kb
input:
8000 add 3540 add 6114 6114 3540 add 7095 6114 3540 7095 add 7142 6114 3540 7095 7142 add 4694 6114 3540 7095 4694 7142 add 1040 6114 3540 7095 1040 add 2503 6114 3540 7095 1040 2503 add 5498 6114 3540 7095 4694 7142 5498 add 4061 6114 3540 7095 4061 4694 7142 5498 add 213 6114 3540 7095 4061 213 7...
output:
0 3540 2 3540 6114 6114 3 6114 7095 3540 6114 4 6114 7142 3540 7095 6114 5 6114 4694 3540 7095 7142 6114 4 6114 1040 3540 7095 6114 5 6114 2503 3540 7095 1040 6114 6 6114 5498 3540 7095 4694 7142 6114 7 6114 4061 3540 7095 4694 7142 5498 6114 6 6114 213 3540 7095 4061 7142 6114 7 6114 300 3540 7095 ...
result:
ok n=8000, OK
Test #42:
score: 0
Accepted
time: 64ms
memory: 3936kb
input:
8000 add 6663 add 7408 7408 6663 add 2088 2088 7408 6663 add 1213 2088 7408 1213 6663 add 3752 3752 2088 7408 1213 6663 add 4898 3752 2088 4898 6663 add 6916 3752 2088 6916 4898 6663 add 3470 3470 3752 2088 7408 6916 1213 add 6588 3470 3752 6588 2088 7408 6916 1213 add 6136 3470 3752 6588 6916 6136...
output:
0 6663 2 6663 7408 7408 3 7408 2088 6663 2088 4 2088 1213 7408 6663 2088 5 2088 3752 7408 6663 1213 3752 4 3752 4898 2088 6663 3752 5 3752 6916 2088 4898 6663 3752 6 3752 3470 2088 6916 7408 1213 3470 7 3470 6588 3752 6916 2088 1213 7408 3470 6 3470 6136 3752 6916 6588 1213 3470 7 3470 3508 3752 691...
result:
ok n=8000, OK
Test #43:
score: 0
Accepted
time: 59ms
memory: 3652kb
input:
8000 add 6663 add 2364 6663 2364 add 7626 6663 7626 2364 add 131 131 6663 7626 2364 add 6567 131 6567 6663 7626 2364 add 6812 131 6567 6812 2364 add 4718 131 6567 4718 6812 2364 add 1312 1312 131 6567 6663 7626 4718 add 5091 1312 5091 131 6567 6663 7626 4718 add 4819 4819 1312 5091 131 7626 4718 ad...
output:
0 6663 2 6663 2364 6663 3 6663 7626 2364 6663 4 6663 131 7626 2364 131 5 131 6567 6663 2364 7626 131 4 131 6812 6567 2364 131 5 131 4718 6567 6812 2364 131 6 131 1312 6567 4718 6663 7626 1312 7 1312 5091 131 4718 6567 7626 6663 1312 6 1312 4819 5091 4718 131 7626 4819 7 4819 1421 1312 4718 5091 131 ...
result:
ok n=8000, OK
Test #44:
score: 0
Accepted
time: 79ms
memory: 3648kb
input:
8000 add 4339 add 615 615 4339 add 7105 615 7105 4339 add 4718 615 7105 4718 4339 add 2503 615 7105 4718 4339 2503 add 4810 615 7105 4810 4339 add 6965 615 7105 4810 4339 6965 add 1700 615 7105 4810 4718 2503 1700 add 533 615 7105 4810 4718 2503 1700 533 add 3145 615 7105 3145 4810 4718 2503 add 62...
output:
0 4339 2 4339 615 615 3 615 7105 4339 615 4 615 4718 7105 4339 615 5 615 2503 7105 4339 4718 615 4 615 4810 7105 4339 615 5 615 6965 7105 4810 4339 615 6 615 1700 7105 4810 4718 2503 615 7 615 533 7105 4810 4718 2503 1700 615 6 615 3145 7105 4810 4718 2503 615 7 615 6288 7105 4810 3145 4718 2503 628...
result:
ok n=8000, OK
Test #45:
score: 0
Accepted
time: 90ms
memory: 3736kb
input:
8000 add 4964 add 3493 4964 3493 add 5110 4964 5110 3493 add 533 4964 533 5110 3493 add 1700 4964 1700 533 5110 3493 add 4277 4964 4277 1700 3493 add 2368 4964 2368 4277 1700 3493 add 4495 4964 4495 2368 4277 1700 3493 add 4305 4964 4305 4495 2368 4277 1700 3493 add 6965 4964 6965 4305 4495 1700 34...
output:
0 4964 2 4964 3493 4964 3 4964 5110 3493 4964 4 4964 533 5110 3493 4964 5 4964 1700 533 3493 5110 4964 4 4964 4277 1700 3493 4964 5 4964 2368 4277 1700 3493 4964 6 4964 4495 2368 1700 4277 3493 4964 7 4964 4305 4495 1700 2368 3493 4277 4964 6 4964 6965 4305 1700 4495 3493 4964 7 4964 2503 6965 1700 ...
result:
ok n=8000, OK