#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, cur, ans[100100], chk[100100];
int dp[100100], opt[100100];
void dnc0(vector<int> a);
void dnc1(vector<int> L, vector<int> R, int onL, int onR);
int myquery(int x){
chk[x] ^= 1;
cur = Query(x);
return cur;
}
void dnc0(vector<int> a){
int c = a.size() / 2;
if (c==0) return;
if (c==1){
ans[a[0]] = a[1];
ans[a[1]] = a[0];
return;
}
vector<int> L, R;
for (auto &x:a){
int prv = cur;
int now = myquery(x);
if (now==prv){
R.push_back(x);
}
else{
L.push_back(x);
}
}
dnc1(L, R, 1, 1);
}
void dnc1(vector<int> L, vector<int> R, int onL, int onR){
int c = L.size();
if (c==0) return;
if (c==1){
ans[L[0]] = R[0];
ans[R[0]] = L[0];
return;
}
vector<int> L1, R1, L2, R2;
for (int i=0;i<opt[c];i++) {L1.push_back(L[i]); myquery(L[i]);}
for (int i=opt[c];i<c;i++) L2.push_back(L[i]);
for (auto &x:R){
if (x==R.back()){
if (L1.size()!=R1.size()) R1.push_back(x);
else R2.push_back(x);
break;
}
int prv = cur;
int delta = myquery(x) - prv;
if ((!onL) == (delta==0)) R1.push_back(x);
else R2.push_back(x);
}
dnc1(L1, R1, !onL, !onR);
dnc1(L2, R2, onL, !onR);
}
void run(int MX){
dp[0] = 0;
dp[1] = 0;
for (int i=2;i<=MX;i++){
dp[i] = 1e9;
opt[i] = -1;
int s = 0.27 * i;
int e = 0.4 * i;
if (i<=100) s = 1, e = i-1;
for (int j=s;j<=e;j++){
int val = j + (i-1) + dp[j] + dp[i-j];
if (val < dp[i]) dp[i] = val, opt[i] = j;
}
}
}
void Solve(int N) {
run(43000);
n = N, cur = 0;
vector<int> a;
for (int i=1;i<=n*2;i++) a.push_back(i);
dnc0(a);
for (int i=1;i<=n*2;i++) if (i < ans[i]) Answer(i, ans[i]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
113 ms |
672 KB |
Output is correct |
2 |
Correct |
104 ms |
900 KB |
Output is correct |
3 |
Correct |
102 ms |
1104 KB |
Output is correct |
4 |
Correct |
113 ms |
1572 KB |
Output is correct |
5 |
Correct |
118 ms |
2352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
15 |
Correct |
134 ms |
4936 KB |
Output is correct |
16 |
Correct |
147 ms |
4964 KB |
Output is correct |
17 |
Correct |
155 ms |
5152 KB |
Output is correct |
18 |
Correct |
131 ms |
4892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
15 |
Correct |
134 ms |
4936 KB |
Output is correct |
16 |
Correct |
147 ms |
4964 KB |
Output is correct |
17 |
Correct |
155 ms |
5152 KB |
Output is correct |
18 |
Correct |
131 ms |
4892 KB |
Output is correct |
19 |
Correct |
137 ms |
5056 KB |
Output is correct |
20 |
Correct |
141 ms |
5116 KB |
Output is correct |
21 |
Correct |
140 ms |
5184 KB |
Output is correct |
22 |
Correct |
146 ms |
4984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
15 |
Correct |
134 ms |
4936 KB |
Output is correct |
16 |
Correct |
147 ms |
4964 KB |
Output is correct |
17 |
Correct |
155 ms |
5152 KB |
Output is correct |
18 |
Correct |
131 ms |
4892 KB |
Output is correct |
19 |
Correct |
137 ms |
5056 KB |
Output is correct |
20 |
Correct |
141 ms |
5116 KB |
Output is correct |
21 |
Correct |
140 ms |
5184 KB |
Output is correct |
22 |
Correct |
146 ms |
4984 KB |
Output is correct |
23 |
Correct |
137 ms |
5136 KB |
Output is correct |
24 |
Correct |
147 ms |
5140 KB |
Output is correct |
25 |
Correct |
140 ms |
5068 KB |
Output is correct |
26 |
Correct |
156 ms |
5036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
15 |
Correct |
134 ms |
4936 KB |
Output is correct |
16 |
Correct |
147 ms |
4964 KB |
Output is correct |
17 |
Correct |
155 ms |
5152 KB |
Output is correct |
18 |
Correct |
131 ms |
4892 KB |
Output is correct |
19 |
Correct |
137 ms |
5056 KB |
Output is correct |
20 |
Correct |
141 ms |
5116 KB |
Output is correct |
21 |
Correct |
140 ms |
5184 KB |
Output is correct |
22 |
Correct |
146 ms |
4984 KB |
Output is correct |
23 |
Correct |
137 ms |
5136 KB |
Output is correct |
24 |
Correct |
147 ms |
5140 KB |
Output is correct |
25 |
Correct |
140 ms |
5068 KB |
Output is correct |
26 |
Correct |
156 ms |
5036 KB |
Output is correct |
27 |
Correct |
140 ms |
5212 KB |
Output is correct |
28 |
Correct |
144 ms |
5204 KB |
Output is correct |
29 |
Correct |
141 ms |
5224 KB |
Output is correct |
30 |
Correct |
133 ms |
5084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
15 |
Correct |
134 ms |
4936 KB |
Output is correct |
16 |
Correct |
147 ms |
4964 KB |
Output is correct |
17 |
Correct |
155 ms |
5152 KB |
Output is correct |
18 |
Correct |
131 ms |
4892 KB |
Output is correct |
19 |
Correct |
137 ms |
5056 KB |
Output is correct |
20 |
Correct |
141 ms |
5116 KB |
Output is correct |
21 |
Correct |
140 ms |
5184 KB |
Output is correct |
22 |
Correct |
146 ms |
4984 KB |
Output is correct |
23 |
Correct |
137 ms |
5136 KB |
Output is correct |
24 |
Correct |
147 ms |
5140 KB |
Output is correct |
25 |
Correct |
140 ms |
5068 KB |
Output is correct |
26 |
Correct |
156 ms |
5036 KB |
Output is correct |
27 |
Correct |
140 ms |
5212 KB |
Output is correct |
28 |
Correct |
144 ms |
5204 KB |
Output is correct |
29 |
Correct |
141 ms |
5224 KB |
Output is correct |
30 |
Correct |
133 ms |
5084 KB |
Output is correct |
31 |
Correct |
156 ms |
5324 KB |
Output is correct |
32 |
Correct |
154 ms |
5352 KB |
Output is correct |
33 |
Correct |
137 ms |
5344 KB |
Output is correct |
34 |
Correct |
139 ms |
5360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
580 KB |
Output is correct |
2 |
Correct |
99 ms |
532 KB |
Output is correct |
3 |
Correct |
103 ms |
852 KB |
Output is correct |
4 |
Correct |
99 ms |
552 KB |
Output is correct |
5 |
Correct |
113 ms |
672 KB |
Output is correct |
6 |
Correct |
104 ms |
900 KB |
Output is correct |
7 |
Correct |
102 ms |
1104 KB |
Output is correct |
8 |
Correct |
113 ms |
1572 KB |
Output is correct |
9 |
Correct |
118 ms |
2352 KB |
Output is correct |
10 |
Correct |
100 ms |
720 KB |
Output is correct |
11 |
Correct |
109 ms |
1792 KB |
Output is correct |
12 |
Correct |
116 ms |
2388 KB |
Output is correct |
13 |
Correct |
114 ms |
2488 KB |
Output is correct |
14 |
Correct |
156 ms |
2288 KB |
Output is correct |
15 |
Correct |
134 ms |
4936 KB |
Output is correct |
16 |
Correct |
147 ms |
4964 KB |
Output is correct |
17 |
Correct |
155 ms |
5152 KB |
Output is correct |
18 |
Correct |
131 ms |
4892 KB |
Output is correct |
19 |
Correct |
137 ms |
5056 KB |
Output is correct |
20 |
Correct |
141 ms |
5116 KB |
Output is correct |
21 |
Correct |
140 ms |
5184 KB |
Output is correct |
22 |
Correct |
146 ms |
4984 KB |
Output is correct |
23 |
Correct |
137 ms |
5136 KB |
Output is correct |
24 |
Correct |
147 ms |
5140 KB |
Output is correct |
25 |
Correct |
140 ms |
5068 KB |
Output is correct |
26 |
Correct |
156 ms |
5036 KB |
Output is correct |
27 |
Correct |
140 ms |
5212 KB |
Output is correct |
28 |
Correct |
144 ms |
5204 KB |
Output is correct |
29 |
Correct |
141 ms |
5224 KB |
Output is correct |
30 |
Correct |
133 ms |
5084 KB |
Output is correct |
31 |
Correct |
156 ms |
5324 KB |
Output is correct |
32 |
Correct |
154 ms |
5352 KB |
Output is correct |
33 |
Correct |
137 ms |
5344 KB |
Output is correct |
34 |
Correct |
139 ms |
5360 KB |
Output is correct |
35 |
Correct |
178 ms |
5456 KB |
Output is correct |
36 |
Correct |
148 ms |
5480 KB |
Output is correct |
37 |
Correct |
137 ms |
5368 KB |
Output is correct |
38 |
Correct |
157 ms |
5368 KB |
Output is correct |