oj.uz

Submission #113882

# Submission time Handle Problem Language Result Execution time Memory
113882 2019-05-29T03:12:14 Z Mamnoon_Siam Minerals (JOI19_minerals) C++17
75 / 100
 1000 ms 4828 KB 
#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:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:36: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:58: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:43:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:85: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 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 15 ms 768 KB Output is correct
4 Correct 47 ms 1184 KB Output is correct
5 Correct 150 ms 1912 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct
15 Correct 894 ms 4544 KB Output is correct
16 Correct 913 ms 4596 KB Output is correct
17 Correct 906 ms 4560 KB Output is correct
18 Correct 885 ms 4272 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct
15 Correct 894 ms 4544 KB Output is correct
16 Correct 913 ms 4596 KB Output is correct
17 Correct 906 ms 4560 KB Output is correct
18 Correct 885 ms 4272 KB Output is correct
19 Correct 951 ms 4768 KB Output is correct
20 Correct 949 ms 4772 KB Output is correct
21 Correct 931 ms 4516 KB Output is correct
22 Correct 923 ms 4440 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct
15 Correct 894 ms 4544 KB Output is correct
16 Correct 913 ms 4596 KB Output is correct
17 Correct 906 ms 4560 KB Output is correct
18 Correct 885 ms 4272 KB Output is correct
19 Correct 951 ms 4768 KB Output is correct
20 Correct 949 ms 4772 KB Output is correct
21 Correct 931 ms 4516 KB Output is correct
22 Correct 923 ms 4440 KB Output is correct
23 Execution timed out 1004 ms 4828 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct
15 Correct 894 ms 4544 KB Output is correct
16 Correct 913 ms 4596 KB Output is correct
17 Correct 906 ms 4560 KB Output is correct
18 Correct 885 ms 4272 KB Output is correct
19 Correct 951 ms 4768 KB Output is correct
20 Correct 949 ms 4772 KB Output is correct
21 Correct 931 ms 4516 KB Output is correct
22 Correct 923 ms 4440 KB Output is correct
23 Execution timed out 1004 ms 4828 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct
15 Correct 894 ms 4544 KB Output is correct
16 Correct 913 ms 4596 KB Output is correct
17 Correct 906 ms 4560 KB Output is correct
18 Correct 885 ms 4272 KB Output is correct
19 Correct 951 ms 4768 KB Output is correct
20 Correct 949 ms 4772 KB Output is correct
21 Correct 931 ms 4516 KB Output is correct
22 Correct 923 ms 4440 KB Output is correct
23 Execution timed out 1004 ms 4828 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 47 ms 1184 KB Output is correct
9 Correct 150 ms 1912 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 72 ms 1448 KB Output is correct
12 Correct 150 ms 1964 KB Output is correct
13 Correct 147 ms 2044 KB Output is correct
14 Correct 150 ms 1884 KB Output is correct
15 Correct 894 ms 4544 KB Output is correct
16 Correct 913 ms 4596 KB Output is correct
17 Correct 906 ms 4560 KB Output is correct
18 Correct 885 ms 4272 KB Output is correct
19 Correct 951 ms 4768 KB Output is correct
20 Correct 949 ms 4772 KB Output is correct
21 Correct 931 ms 4516 KB Output is correct
22 Correct 923 ms 4440 KB Output is correct
23 Execution timed out 1004 ms 4828 KB Time limit exceeded
24 Halted 0 ms 0 KB -