oj.uz

Submission #113889

# Submission time Handle Problem Language Result Execution time Memory
113889 2019-05-29T03:44:29 Z Mamnoon_Siam Minerals (JOI19_minerals) C++17
100 / 100
 771 ms 5072 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 43000 + 5;
int dp[maxn], opt[maxn];

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);
	vector<int> 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]);
		} else {
			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 - 1;
		opt[i] = arg;
	}
	/* In worst case scenario, maximum number
	   of calls to Query() is dp[N] + 2N - 1. */
	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:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:32: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:55: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:39:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:82: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 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 12 ms 768 KB Output is correct
4 Correct 34 ms 1144 KB Output is correct
5 Correct 106 ms 1844 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct
15 Correct 594 ms 4644 KB Output is correct
16 Correct 632 ms 4596 KB Output is correct
17 Correct 583 ms 4388 KB Output is correct
18 Correct 585 ms 4144 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct
15 Correct 594 ms 4644 KB Output is correct
16 Correct 632 ms 4596 KB Output is correct
17 Correct 583 ms 4388 KB Output is correct
18 Correct 585 ms 4144 KB Output is correct
19 Correct 616 ms 4744 KB Output is correct
20 Correct 613 ms 4748 KB Output is correct
21 Correct 605 ms 4440 KB Output is correct
22 Correct 623 ms 4344 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct
15 Correct 594 ms 4644 KB Output is correct
16 Correct 632 ms 4596 KB Output is correct
17 Correct 583 ms 4388 KB Output is correct
18 Correct 585 ms 4144 KB Output is correct
19 Correct 616 ms 4744 KB Output is correct
20 Correct 613 ms 4748 KB Output is correct
21 Correct 605 ms 4440 KB Output is correct
22 Correct 623 ms 4344 KB Output is correct
23 Correct 647 ms 4844 KB Output is correct
24 Correct 670 ms 4856 KB Output is correct
25 Correct 657 ms 4568 KB Output is correct
26 Correct 630 ms 4388 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct
15 Correct 594 ms 4644 KB Output is correct
16 Correct 632 ms 4596 KB Output is correct
17 Correct 583 ms 4388 KB Output is correct
18 Correct 585 ms 4144 KB Output is correct
19 Correct 616 ms 4744 KB Output is correct
20 Correct 613 ms 4748 KB Output is correct
21 Correct 605 ms 4440 KB Output is correct
22 Correct 623 ms 4344 KB Output is correct
23 Correct 647 ms 4844 KB Output is correct
24 Correct 670 ms 4856 KB Output is correct
25 Correct 657 ms 4568 KB Output is correct
26 Correct 630 ms 4388 KB Output is correct
27 Correct 677 ms 4752 KB Output is correct
28 Correct 676 ms 4980 KB Output is correct
29 Correct 675 ms 4564 KB Output is correct
30 Correct 672 ms 4372 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct
15 Correct 594 ms 4644 KB Output is correct
16 Correct 632 ms 4596 KB Output is correct
17 Correct 583 ms 4388 KB Output is correct
18 Correct 585 ms 4144 KB Output is correct
19 Correct 616 ms 4744 KB Output is correct
20 Correct 613 ms 4748 KB Output is correct
21 Correct 605 ms 4440 KB Output is correct
22 Correct 623 ms 4344 KB Output is correct
23 Correct 647 ms 4844 KB Output is correct
24 Correct 670 ms 4856 KB Output is correct
25 Correct 657 ms 4568 KB Output is correct
26 Correct 630 ms 4388 KB Output is correct
27 Correct 677 ms 4752 KB Output is correct
28 Correct 676 ms 4980 KB Output is correct
29 Correct 675 ms 4564 KB Output is correct
30 Correct 672 ms 4372 KB Output is correct
31 Correct 707 ms 4852 KB Output is correct
32 Correct 721 ms 4900 KB Output is correct
33 Correct 699 ms 4684 KB Output is correct
34 Correct 692 ms 4372 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 12 ms 768 KB Output is correct
8 Correct 34 ms 1144 KB Output is correct
9 Correct 106 ms 1844 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 1344 KB Output is correct
12 Correct 104 ms 1912 KB Output is correct
13 Correct 100 ms 1912 KB Output is correct
14 Correct 101 ms 1944 KB Output is correct
15 Correct 594 ms 4644 KB Output is correct
16 Correct 632 ms 4596 KB Output is correct
17 Correct 583 ms 4388 KB Output is correct
18 Correct 585 ms 4144 KB Output is correct
19 Correct 616 ms 4744 KB Output is correct
20 Correct 613 ms 4748 KB Output is correct
21 Correct 605 ms 4440 KB Output is correct
22 Correct 623 ms 4344 KB Output is correct
23 Correct 647 ms 4844 KB Output is correct
24 Correct 670 ms 4856 KB Output is correct
25 Correct 657 ms 4568 KB Output is correct
26 Correct 630 ms 4388 KB Output is correct
27 Correct 677 ms 4752 KB Output is correct
28 Correct 676 ms 4980 KB Output is correct
29 Correct 675 ms 4564 KB Output is correct
30 Correct 672 ms 4372 KB Output is correct
31 Correct 707 ms 4852 KB Output is correct
32 Correct 721 ms 4900 KB Output is correct
33 Correct 699 ms 4684 KB Output is correct
34 Correct 692 ms 4372 KB Output is correct
35 Correct 747 ms 5072 KB Output is correct
36 Correct 745 ms 4948 KB Output is correct
37 Correct 742 ms 4796 KB Output is correct
38 Correct 771 ms 4496 KB Output is correct