oj.uz

Submission #113883

# Submission time Handle Problem Language Result Execution time Memory
113883 2019-05-29T03:13:06 Z Mamnoon_Siam Minerals (JOI19_minerals) C++17
100 / 100
 755 ms 5004 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 45000;
int dp[maxn], opt[maxn];

mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
struct RNG {
	int operator () (int n) {
		return rnd(n);
	}
};

void solve(vector<int> u, vector<int> v, int f) {
	if(u.empty()) return;

	if(u.size() == 1) {
		Answer(u.back(), v.back());
		return;
	}
	int mid, last;
	if(f) {
		mid = u.size() - opt[u.size()];
		for(int i = mid; i < v.size(); i++) {
			last = Query(v[i]);
		}
	} else {
		mid = opt[u.size()];
		for(int i = 0; i < mid; i++) {
			last = Query(v[i]);
		}
	}
	vector<int> lu, lv(v.begin(), v.begin() + mid), ru, rv(v.begin() + mid, v.end());
	for(int i = 0; i < u.size(); i++) {
		if(lu.size() == lv.size()) {
			ru.emplace_back(u[i]);
		} else if(ru.size() == rv.size()) {
			lu.emplace_back(u[i]);
		} else {
			int rep = Query(u[i]);
			if(rep == last) {
				lu.emplace_back(u[i]);
			} else {
				ru.emplace_back(u[i]);
			}
			last = rep;
		}
	}
	solve(lu, lv, 1);
	solve(ru, rv, 0);
}

void split(vector<int> v) {
	vector<int> l, r;
	int last = -1;
	for(int i = 0; i < v.size(); i++) {
		if(r.size() == v.size() / 2) {
			l.emplace_back(v[i]);
			continue;
		}
		int rep = Query(v[i]);
		if(rep == last) {
			l.emplace_back(v[i]);
		} else {
			r.emplace_back(v[i]);
		} last = rep;
	}
	solve(l, r, 1);
}

void Solve(int N) {
	dp[1] = 0;
	for(int i = 2; i <= N; i++) {
		int mn = INT_MAX, tmp, arg, cmp = (i - 1) / 2 + 1;
		for(int j = 1; j < i; j++) {
			tmp = dp[j] + dp[i - j] + (j < cmp ? j : i - j);
			if(tmp < mn) {
				mn = tmp;
				arg = j;
			}
		}
		dp[i] = mn + i;
		opt[i] = arg;
	}
	vector<int> v(2 * N);
	iota(v.begin(), v.end(), 1);
	split(v);
}

Compilation message

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void split(std::vector<int>)':
minerals.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:45:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:87:10: warning: 'arg' may be used uninitialized in this function [-Wmaybe-uninitialized]
   opt[i] = arg;
   ~~~~~~~^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 536 KB Output is correct
3 Correct 13 ms 640 KB Output is correct
4 Correct 35 ms 1144 KB Output is correct
5 Correct 112 ms 1928 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct
15 Correct 597 ms 4724 KB Output is correct
16 Correct 593 ms 4596 KB Output is correct
17 Correct 592 ms 4552 KB Output is correct
18 Correct 583 ms 4144 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct
15 Correct 597 ms 4724 KB Output is correct
16 Correct 593 ms 4596 KB Output is correct
17 Correct 592 ms 4552 KB Output is correct
18 Correct 583 ms 4144 KB Output is correct
19 Correct 622 ms 4796 KB Output is correct
20 Correct 650 ms 4620 KB Output is correct
21 Correct 610 ms 4540 KB Output is correct
22 Correct 609 ms 4252 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct
15 Correct 597 ms 4724 KB Output is correct
16 Correct 593 ms 4596 KB Output is correct
17 Correct 592 ms 4552 KB Output is correct
18 Correct 583 ms 4144 KB Output is correct
19 Correct 622 ms 4796 KB Output is correct
20 Correct 650 ms 4620 KB Output is correct
21 Correct 610 ms 4540 KB Output is correct
22 Correct 609 ms 4252 KB Output is correct
23 Correct 648 ms 4764 KB Output is correct
24 Correct 664 ms 4852 KB Output is correct
25 Correct 646 ms 4656 KB Output is correct
26 Correct 645 ms 4424 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct
15 Correct 597 ms 4724 KB Output is correct
16 Correct 593 ms 4596 KB Output is correct
17 Correct 592 ms 4552 KB Output is correct
18 Correct 583 ms 4144 KB Output is correct
19 Correct 622 ms 4796 KB Output is correct
20 Correct 650 ms 4620 KB Output is correct
21 Correct 610 ms 4540 KB Output is correct
22 Correct 609 ms 4252 KB Output is correct
23 Correct 648 ms 4764 KB Output is correct
24 Correct 664 ms 4852 KB Output is correct
25 Correct 646 ms 4656 KB Output is correct
26 Correct 645 ms 4424 KB Output is correct
27 Correct 679 ms 4864 KB Output is correct
28 Correct 671 ms 5004 KB Output is correct
29 Correct 664 ms 4732 KB Output is correct
30 Correct 689 ms 4416 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct
15 Correct 597 ms 4724 KB Output is correct
16 Correct 593 ms 4596 KB Output is correct
17 Correct 592 ms 4552 KB Output is correct
18 Correct 583 ms 4144 KB Output is correct
19 Correct 622 ms 4796 KB Output is correct
20 Correct 650 ms 4620 KB Output is correct
21 Correct 610 ms 4540 KB Output is correct
22 Correct 609 ms 4252 KB Output is correct
23 Correct 648 ms 4764 KB Output is correct
24 Correct 664 ms 4852 KB Output is correct
25 Correct 646 ms 4656 KB Output is correct
26 Correct 645 ms 4424 KB Output is correct
27 Correct 679 ms 4864 KB Output is correct
28 Correct 671 ms 5004 KB Output is correct
29 Correct 664 ms 4732 KB Output is correct
30 Correct 689 ms 4416 KB Output is correct
31 Correct 704 ms 4896 KB Output is correct
32 Correct 719 ms 4996 KB Output is correct
33 Correct 706 ms 4768 KB Output is correct
34 Correct 710 ms 4520 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 35 ms 1144 KB Output is correct
9 Correct 112 ms 1928 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 51 ms 1528 KB Output is correct
12 Correct 104 ms 2040 KB Output is correct
13 Correct 100 ms 2072 KB Output is correct
14 Correct 101 ms 1856 KB Output is correct
15 Correct 597 ms 4724 KB Output is correct
16 Correct 593 ms 4596 KB Output is correct
17 Correct 592 ms 4552 KB Output is correct
18 Correct 583 ms 4144 KB Output is correct
19 Correct 622 ms 4796 KB Output is correct
20 Correct 650 ms 4620 KB Output is correct
21 Correct 610 ms 4540 KB Output is correct
22 Correct 609 ms 4252 KB Output is correct
23 Correct 648 ms 4764 KB Output is correct
24 Correct 664 ms 4852 KB Output is correct
25 Correct 646 ms 4656 KB Output is correct
26 Correct 645 ms 4424 KB Output is correct
27 Correct 679 ms 4864 KB Output is correct
28 Correct 671 ms 5004 KB Output is correct
29 Correct 664 ms 4732 KB Output is correct
30 Correct 689 ms 4416 KB Output is correct
31 Correct 704 ms 4896 KB Output is correct
32 Correct 719 ms 4996 KB Output is correct
33 Correct 706 ms 4768 KB Output is correct
34 Correct 710 ms 4520 KB Output is correct
35 Correct 740 ms 4888 KB Output is correct
36 Correct 755 ms 4836 KB Output is correct
37 Correct 739 ms 4768 KB Output is correct
38 Correct 727 ms 4616 KB Output is correct