#include "minerals.h"
#include<vector>
#include<set>
#include<random>
#include<algorithm>
#include<iostream>
using namespace std;
int n, s;
//2nlog(2n)
random_device rd;
mt19937 g(rd());
int szdp = 43002;//getting the szdp bigger, trinary search
int dp0[43005] ,nxt0[43005];
int cut[86005];
void solve(vector<int>& in, int s, int e, vector<int>& rest, int f1) {
if (in.size() == 1) { Answer(in[0], rest[0]); return; }
vector<int> in1, in2;
int sz1 = 2 * in.size() / 3;
if (in.size() <= szdp) sz1 = in.size() - nxt0[in.size()];
int sz = 0;
if (f1) {
for (int i = 0; i < sz1; i++) in1.push_back(in[i]);
for (int i = sz1; i < in.size(); i++) in2.push_back(in[i]);
for (int i : in2) sz = Query(i);
}
else {
sz1 = in.size() - sz1;
for (int i = 0; i < sz1; i++) in1.push_back(in[i]);
for (int i = sz1; i < in.size(); i++) in2.push_back(in[i]);
for (int i : in1) sz = Query(i);
}
vector<int> rest1, rest2;
int m = s + sz1 - 1;
for (int j : rest) {
if(cut[j] <= m) { rest1.push_back(j); continue; }
if (rest1.size() == sz1){ rest2.push_back(j); continue; }
if (rest2.size() == rest.size()-sz1) { rest1.push_back(j); continue; }
int u = Query(j);
if (u == sz) rest1.push_back(j);
else {
rest2.push_back(j);
sz = u;
}
}
solve(in1, s, m, rest1, 1);
solve(in2, m+1, e, rest2, 0);
}
void Solve(int N) {
dp0[1] = 0;
for (int i = 2; i <= szdp; i++) {
int l = 1, r = i / 2, m;
while (r > l) {
m = (l + r) / 2;
int vm = dp0[m] + dp0[i - m] + m + i;
int vm1 = dp0[m+1] + dp0[i - m - 1] + m + 1 + i;
if (vm > vm1) l = m + 1;
else r = m;
}
dp0[i] = dp0[l] + dp0[i - l] + l + i;
nxt0[i] = l;
//if (dp1[i] != dp[i]) { cout << i << ' ' << dp[i] << ' ' << dp1[i] << ' ' << "ERROR!!!" << endl; break; }
}
//for (int u = 38000; u <= 44000; u += 1000) cout << u << ' ' << 2 * u + dp0[u] << endl;
n = N; s = n << 1;
int sz = 0;
vector<int> in, rest;
vector<int> vec(s);
for (int i = 0; i < s; i++)vec[i] = i + 1;
shuffle(vec.begin(), vec.end(), g);
for (int i : vec) {
if (in.size() < n) {
int u = Query(i);
if (u > sz) {
sz = u;
in.push_back(i);
}
else {
rest.push_back(i);
cut[i] = in.size();
}
}
else {
rest.push_back(i);
cut[i] = in.size();
}
}
solve(in, 0, n-1, rest, 1);
}
Compilation message
minerals.cpp: In function 'void solve(std::vector<int>&, int, int, std::vector<int>&, int)':
minerals.cpp:21:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
21 | if (in.size() <= szdp) sz1 = in.size() - nxt0[in.size()];
| ~~~~~~~~~~^~~~~~~
minerals.cpp:26:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = sz1; i < in.size(); i++) in2.push_back(in[i]);
| ~~^~~~~~~~~~~
minerals.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = sz1; i < in.size(); i++) in2.push_back(in[i]);
| ~~^~~~~~~~~~~
minerals.cpp:40:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
40 | if (rest1.size() == sz1){ rest2.push_back(j); continue; }
| ~~~~~~~~~~~~~^~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:79:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
79 | if (in.size() < n) {
| ~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
856 KB |
Output is correct |
2 |
Correct |
4 ms |
856 KB |
Output is correct |
3 |
Correct |
6 ms |
1112 KB |
Output is correct |
4 |
Correct |
8 ms |
1368 KB |
Output is correct |
5 |
Correct |
14 ms |
1936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
15 |
Correct |
34 ms |
3952 KB |
Output is correct |
16 |
Correct |
34 ms |
3920 KB |
Output is correct |
17 |
Correct |
35 ms |
4276 KB |
Output is correct |
18 |
Correct |
32 ms |
3672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
15 |
Correct |
34 ms |
3952 KB |
Output is correct |
16 |
Correct |
34 ms |
3920 KB |
Output is correct |
17 |
Correct |
35 ms |
4276 KB |
Output is correct |
18 |
Correct |
32 ms |
3672 KB |
Output is correct |
19 |
Correct |
33 ms |
4068 KB |
Output is correct |
20 |
Correct |
34 ms |
3832 KB |
Output is correct |
21 |
Correct |
35 ms |
4320 KB |
Output is correct |
22 |
Correct |
41 ms |
3960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
15 |
Correct |
34 ms |
3952 KB |
Output is correct |
16 |
Correct |
34 ms |
3920 KB |
Output is correct |
17 |
Correct |
35 ms |
4276 KB |
Output is correct |
18 |
Correct |
32 ms |
3672 KB |
Output is correct |
19 |
Correct |
33 ms |
4068 KB |
Output is correct |
20 |
Correct |
34 ms |
3832 KB |
Output is correct |
21 |
Correct |
35 ms |
4320 KB |
Output is correct |
22 |
Correct |
41 ms |
3960 KB |
Output is correct |
23 |
Correct |
34 ms |
4176 KB |
Output is correct |
24 |
Correct |
35 ms |
4080 KB |
Output is correct |
25 |
Correct |
34 ms |
4264 KB |
Output is correct |
26 |
Correct |
39 ms |
4660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
15 |
Correct |
34 ms |
3952 KB |
Output is correct |
16 |
Correct |
34 ms |
3920 KB |
Output is correct |
17 |
Correct |
35 ms |
4276 KB |
Output is correct |
18 |
Correct |
32 ms |
3672 KB |
Output is correct |
19 |
Correct |
33 ms |
4068 KB |
Output is correct |
20 |
Correct |
34 ms |
3832 KB |
Output is correct |
21 |
Correct |
35 ms |
4320 KB |
Output is correct |
22 |
Correct |
41 ms |
3960 KB |
Output is correct |
23 |
Correct |
34 ms |
4176 KB |
Output is correct |
24 |
Correct |
35 ms |
4080 KB |
Output is correct |
25 |
Correct |
34 ms |
4264 KB |
Output is correct |
26 |
Correct |
39 ms |
4660 KB |
Output is correct |
27 |
Correct |
38 ms |
4176 KB |
Output is correct |
28 |
Correct |
35 ms |
4184 KB |
Output is correct |
29 |
Correct |
36 ms |
4584 KB |
Output is correct |
30 |
Correct |
36 ms |
4132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
15 |
Correct |
34 ms |
3952 KB |
Output is correct |
16 |
Correct |
34 ms |
3920 KB |
Output is correct |
17 |
Correct |
35 ms |
4276 KB |
Output is correct |
18 |
Correct |
32 ms |
3672 KB |
Output is correct |
19 |
Correct |
33 ms |
4068 KB |
Output is correct |
20 |
Correct |
34 ms |
3832 KB |
Output is correct |
21 |
Correct |
35 ms |
4320 KB |
Output is correct |
22 |
Correct |
41 ms |
3960 KB |
Output is correct |
23 |
Correct |
34 ms |
4176 KB |
Output is correct |
24 |
Correct |
35 ms |
4080 KB |
Output is correct |
25 |
Correct |
34 ms |
4264 KB |
Output is correct |
26 |
Correct |
39 ms |
4660 KB |
Output is correct |
27 |
Correct |
38 ms |
4176 KB |
Output is correct |
28 |
Correct |
35 ms |
4184 KB |
Output is correct |
29 |
Correct |
36 ms |
4584 KB |
Output is correct |
30 |
Correct |
36 ms |
4132 KB |
Output is correct |
31 |
Correct |
45 ms |
4212 KB |
Output is correct |
32 |
Correct |
43 ms |
4192 KB |
Output is correct |
33 |
Correct |
37 ms |
4484 KB |
Output is correct |
34 |
Correct |
37 ms |
4304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
4 ms |
676 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1112 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
14 ms |
1936 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
10 ms |
1624 KB |
Output is correct |
12 |
Correct |
15 ms |
2104 KB |
Output is correct |
13 |
Correct |
16 ms |
1880 KB |
Output is correct |
14 |
Correct |
14 ms |
2016 KB |
Output is correct |
15 |
Correct |
34 ms |
3952 KB |
Output is correct |
16 |
Correct |
34 ms |
3920 KB |
Output is correct |
17 |
Correct |
35 ms |
4276 KB |
Output is correct |
18 |
Correct |
32 ms |
3672 KB |
Output is correct |
19 |
Correct |
33 ms |
4068 KB |
Output is correct |
20 |
Correct |
34 ms |
3832 KB |
Output is correct |
21 |
Correct |
35 ms |
4320 KB |
Output is correct |
22 |
Correct |
41 ms |
3960 KB |
Output is correct |
23 |
Correct |
34 ms |
4176 KB |
Output is correct |
24 |
Correct |
35 ms |
4080 KB |
Output is correct |
25 |
Correct |
34 ms |
4264 KB |
Output is correct |
26 |
Correct |
39 ms |
4660 KB |
Output is correct |
27 |
Correct |
38 ms |
4176 KB |
Output is correct |
28 |
Correct |
35 ms |
4184 KB |
Output is correct |
29 |
Correct |
36 ms |
4584 KB |
Output is correct |
30 |
Correct |
36 ms |
4132 KB |
Output is correct |
31 |
Correct |
45 ms |
4212 KB |
Output is correct |
32 |
Correct |
43 ms |
4192 KB |
Output is correct |
33 |
Correct |
37 ms |
4484 KB |
Output is correct |
34 |
Correct |
37 ms |
4304 KB |
Output is correct |
35 |
Correct |
40 ms |
4244 KB |
Output is correct |
36 |
Correct |
37 ms |
4244 KB |
Output is correct |
37 |
Correct |
36 ms |
4332 KB |
Output is correct |
38 |
Correct |
35 ms |
3928 KB |
Output is correct |