#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const double RAT=1.618;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[MAXN],res[MAXN],n,bit[MAXN];
vector<int> mid[MAXN];
int query(int now){
int ret=0;
for(int i=now;i>0;i-=(i&(-i)))ret+=bit[i];
return ret;
}
void update(int now,int val){
for(int i=now;i<=n;i+=(i&(-i)))bit[i]+=val;
}
int binser(int x){
int now=0;
for(int i=17;i>=0;i--){
if(now+(1<<i)<=n && bit[now+(1<<i)]<x){
now+=(1<<i);
x-=bit[now];
}
}
return now+1;
}
int tengah(int x,int y){
int L=query(x-1)+1,R=query(y),T;
T=(3*L+2*R)/5;
return binser(T);
}
void Solve(int N) {
int prev=0,tmpL=1,tmpR=N+1,nxt,sudah=0,C=0;
n=N;
vector<int> v;
for(int i=1;i<=2*N;i++)v.push_back(i);
random_shuffle(v.begin(),v.end());
for(auto i : v){
if(tmpL==N+1 || Query(i)==prev){
arr[tmpR]=i;
lo[tmpR]=C+1;
hi[tmpR]=tmpL-1;
if(lo[tmpR]<hi[tmpR])mid[tengah(lo[tmpR],hi[tmpR])].push_back(tmpR);
else{
Answer(i,arr[tmpL-1]);
update(tmpL-1,-1);
arr[tmpL-1]=0;
sudah++;
}
tmpR++;
if(tmpL==tmpR-N)C=tmpL-1;
}
else{
update(tmpL,1);
arr[tmpL]=i;
tmpL++;
prev++;
}
}
if(sudah==N)return;
int prefix=0;
while(sudah<N){
for(int i=1;i<=N;i++){
if(arr[i])prev=Query(arr[i]);
while(!mid[i].empty()){
int now=mid[i].back();
mid[i].pop_back();
nxt=Query(arr[now]);
if(prefix){
if(nxt==prev){ //sudah ada
hi[now]=i;
res[now]=i;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[now]=0;arr[res[now]]=0;
}
}
else{
lo[now]=i+1;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[now]=0;arr[res[now]]=0;
}
}
}
else{
if(nxt==prev){
lo[now]=i+1;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[now]=0;arr[res[now]]=0;
}
}
else{
hi[now]=i;
res[now]=i;
if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
else{
sudah++;
res[now]=binser(query(hi[now]));
Answer(arr[now],arr[res[now]]);
update(res[now],-1);
arr[now]=0;arr[res[now]]=0;
}
}
}
if(sudah==N)return;
prev=nxt;
}
}
prefix=1-prefix;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2552 KB |
Output is correct |
2 |
Correct |
8 ms |
2552 KB |
Output is correct |
3 |
Correct |
14 ms |
2680 KB |
Output is correct |
4 |
Correct |
28 ms |
3196 KB |
Output is correct |
5 |
Correct |
57 ms |
4040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
15 |
Correct |
171 ms |
6812 KB |
Output is correct |
16 |
Correct |
171 ms |
6864 KB |
Output is correct |
17 |
Correct |
170 ms |
6640 KB |
Output is correct |
18 |
Correct |
168 ms |
6524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
15 |
Correct |
171 ms |
6812 KB |
Output is correct |
16 |
Correct |
171 ms |
6864 KB |
Output is correct |
17 |
Correct |
170 ms |
6640 KB |
Output is correct |
18 |
Correct |
168 ms |
6524 KB |
Output is correct |
19 |
Correct |
177 ms |
6692 KB |
Output is correct |
20 |
Correct |
190 ms |
6728 KB |
Output is correct |
21 |
Correct |
168 ms |
6844 KB |
Output is correct |
22 |
Correct |
167 ms |
6636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
15 |
Correct |
171 ms |
6812 KB |
Output is correct |
16 |
Correct |
171 ms |
6864 KB |
Output is correct |
17 |
Correct |
170 ms |
6640 KB |
Output is correct |
18 |
Correct |
168 ms |
6524 KB |
Output is correct |
19 |
Correct |
177 ms |
6692 KB |
Output is correct |
20 |
Correct |
190 ms |
6728 KB |
Output is correct |
21 |
Correct |
168 ms |
6844 KB |
Output is correct |
22 |
Correct |
167 ms |
6636 KB |
Output is correct |
23 |
Correct |
182 ms |
6996 KB |
Output is correct |
24 |
Correct |
178 ms |
6892 KB |
Output is correct |
25 |
Correct |
171 ms |
6864 KB |
Output is correct |
26 |
Correct |
194 ms |
6740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
15 |
Correct |
171 ms |
6812 KB |
Output is correct |
16 |
Correct |
171 ms |
6864 KB |
Output is correct |
17 |
Correct |
170 ms |
6640 KB |
Output is correct |
18 |
Correct |
168 ms |
6524 KB |
Output is correct |
19 |
Correct |
177 ms |
6692 KB |
Output is correct |
20 |
Correct |
190 ms |
6728 KB |
Output is correct |
21 |
Correct |
168 ms |
6844 KB |
Output is correct |
22 |
Correct |
167 ms |
6636 KB |
Output is correct |
23 |
Correct |
182 ms |
6996 KB |
Output is correct |
24 |
Correct |
178 ms |
6892 KB |
Output is correct |
25 |
Correct |
171 ms |
6864 KB |
Output is correct |
26 |
Correct |
194 ms |
6740 KB |
Output is correct |
27 |
Correct |
183 ms |
7076 KB |
Output is correct |
28 |
Correct |
184 ms |
7024 KB |
Output is correct |
29 |
Correct |
178 ms |
7024 KB |
Output is correct |
30 |
Correct |
195 ms |
6920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
15 |
Correct |
171 ms |
6812 KB |
Output is correct |
16 |
Correct |
171 ms |
6864 KB |
Output is correct |
17 |
Correct |
170 ms |
6640 KB |
Output is correct |
18 |
Correct |
168 ms |
6524 KB |
Output is correct |
19 |
Correct |
177 ms |
6692 KB |
Output is correct |
20 |
Correct |
190 ms |
6728 KB |
Output is correct |
21 |
Correct |
168 ms |
6844 KB |
Output is correct |
22 |
Correct |
167 ms |
6636 KB |
Output is correct |
23 |
Correct |
182 ms |
6996 KB |
Output is correct |
24 |
Correct |
178 ms |
6892 KB |
Output is correct |
25 |
Correct |
171 ms |
6864 KB |
Output is correct |
26 |
Correct |
194 ms |
6740 KB |
Output is correct |
27 |
Correct |
183 ms |
7076 KB |
Output is correct |
28 |
Correct |
184 ms |
7024 KB |
Output is correct |
29 |
Correct |
178 ms |
7024 KB |
Output is correct |
30 |
Correct |
195 ms |
6920 KB |
Output is correct |
31 |
Correct |
187 ms |
7072 KB |
Output is correct |
32 |
Correct |
194 ms |
7152 KB |
Output is correct |
33 |
Correct |
182 ms |
7080 KB |
Output is correct |
34 |
Correct |
183 ms |
6896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2552 KB |
Output is correct |
6 |
Correct |
8 ms |
2552 KB |
Output is correct |
7 |
Correct |
14 ms |
2680 KB |
Output is correct |
8 |
Correct |
28 ms |
3196 KB |
Output is correct |
9 |
Correct |
57 ms |
4040 KB |
Output is correct |
10 |
Correct |
6 ms |
2424 KB |
Output is correct |
11 |
Correct |
35 ms |
3448 KB |
Output is correct |
12 |
Correct |
56 ms |
4088 KB |
Output is correct |
13 |
Correct |
56 ms |
4008 KB |
Output is correct |
14 |
Correct |
58 ms |
3964 KB |
Output is correct |
15 |
Correct |
171 ms |
6812 KB |
Output is correct |
16 |
Correct |
171 ms |
6864 KB |
Output is correct |
17 |
Correct |
170 ms |
6640 KB |
Output is correct |
18 |
Correct |
168 ms |
6524 KB |
Output is correct |
19 |
Correct |
177 ms |
6692 KB |
Output is correct |
20 |
Correct |
190 ms |
6728 KB |
Output is correct |
21 |
Correct |
168 ms |
6844 KB |
Output is correct |
22 |
Correct |
167 ms |
6636 KB |
Output is correct |
23 |
Correct |
182 ms |
6996 KB |
Output is correct |
24 |
Correct |
178 ms |
6892 KB |
Output is correct |
25 |
Correct |
171 ms |
6864 KB |
Output is correct |
26 |
Correct |
194 ms |
6740 KB |
Output is correct |
27 |
Correct |
183 ms |
7076 KB |
Output is correct |
28 |
Correct |
184 ms |
7024 KB |
Output is correct |
29 |
Correct |
178 ms |
7024 KB |
Output is correct |
30 |
Correct |
195 ms |
6920 KB |
Output is correct |
31 |
Correct |
187 ms |
7072 KB |
Output is correct |
32 |
Correct |
194 ms |
7152 KB |
Output is correct |
33 |
Correct |
182 ms |
7080 KB |
Output is correct |
34 |
Correct |
183 ms |
6896 KB |
Output is correct |
35 |
Correct |
193 ms |
7272 KB |
Output is correct |
36 |
Correct |
192 ms |
7304 KB |
Output is correct |
37 |
Correct |
194 ms |
7200 KB |
Output is correct |
38 |
Correct |
192 ms |
7184 KB |
Output is correct |