oj.uz

Submission #114160

# Submission time Handle Problem Language Result Execution time Memory
114160 2019-05-30T22:14:53 Z Mamnoon_Siam Minerals (JOI19_minerals) C++17
100 / 100
 406 ms 4980 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.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]);				// <  This part reduces Query()
		} else if(ru.size() == rv.size()) {		// <  call by at least N - 1
			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) { 	// <  This part reduces Query()
			l.emplace_back(v[i]);		// <  call by at least 1
		} 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;
		const int cmp = (i - 1) / 2 + 1;
		for(int j = 1; j <= cmp; 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:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:31: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:54: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:38: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 2 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 4 ms 512 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 22 ms 1152 KB Output is correct
5 Correct 61 ms 1912 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 KB Output is correct
15 Correct 334 ms 4568 KB Output is correct
16 Correct 332 ms 4524 KB Output is correct
17 Correct 319 ms 4416 KB Output is correct
18 Correct 317 ms 4228 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 KB Output is correct
15 Correct 334 ms 4568 KB Output is correct
16 Correct 332 ms 4524 KB Output is correct
17 Correct 319 ms 4416 KB Output is correct
18 Correct 317 ms 4228 KB Output is correct
19 Correct 370 ms 4684 KB Output is correct
20 Correct 337 ms 4792 KB Output is correct
21 Correct 328 ms 4508 KB Output is correct
22 Correct 326 ms 4228 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 KB Output is correct
15 Correct 334 ms 4568 KB Output is correct
16 Correct 332 ms 4524 KB Output is correct
17 Correct 319 ms 4416 KB Output is correct
18 Correct 317 ms 4228 KB Output is correct
19 Correct 370 ms 4684 KB Output is correct
20 Correct 337 ms 4792 KB Output is correct
21 Correct 328 ms 4508 KB Output is correct
22 Correct 326 ms 4228 KB Output is correct
23 Correct 358 ms 4748 KB Output is correct
24 Correct 362 ms 4724 KB Output is correct
25 Correct 339 ms 4488 KB Output is correct
26 Correct 344 ms 4348 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 KB Output is correct
15 Correct 334 ms 4568 KB Output is correct
16 Correct 332 ms 4524 KB Output is correct
17 Correct 319 ms 4416 KB Output is correct
18 Correct 317 ms 4228 KB Output is correct
19 Correct 370 ms 4684 KB Output is correct
20 Correct 337 ms 4792 KB Output is correct
21 Correct 328 ms 4508 KB Output is correct
22 Correct 326 ms 4228 KB Output is correct
23 Correct 358 ms 4748 KB Output is correct
24 Correct 362 ms 4724 KB Output is correct
25 Correct 339 ms 4488 KB Output is correct
26 Correct 344 ms 4348 KB Output is correct
27 Correct 366 ms 4860 KB Output is correct
28 Correct 366 ms 4724 KB Output is correct
29 Correct 360 ms 4616 KB Output is correct
30 Correct 354 ms 4340 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 KB Output is correct
15 Correct 334 ms 4568 KB Output is correct
16 Correct 332 ms 4524 KB Output is correct
17 Correct 319 ms 4416 KB Output is correct
18 Correct 317 ms 4228 KB Output is correct
19 Correct 370 ms 4684 KB Output is correct
20 Correct 337 ms 4792 KB Output is correct
21 Correct 328 ms 4508 KB Output is correct
22 Correct 326 ms 4228 KB Output is correct
23 Correct 358 ms 4748 KB Output is correct
24 Correct 362 ms 4724 KB Output is correct
25 Correct 339 ms 4488 KB Output is correct
26 Correct 344 ms 4348 KB Output is correct
27 Correct 366 ms 4860 KB Output is correct
28 Correct 366 ms 4724 KB Output is correct
29 Correct 360 ms 4616 KB Output is correct
30 Correct 354 ms 4340 KB Output is correct
31 Correct 383 ms 4868 KB Output is correct
32 Correct 386 ms 4980 KB Output is correct
33 Correct 374 ms 4716 KB Output is correct
34 Correct 377 ms 4468 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 2 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 4 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Correct 61 ms 1912 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 34 ms 1408 KB Output is correct
12 Correct 63 ms 2040 KB Output is correct
13 Correct 58 ms 1960 KB Output is correct
14 Correct 58 ms 1784 KB Output is correct
15 Correct 334 ms 4568 KB Output is correct
16 Correct 332 ms 4524 KB Output is correct
17 Correct 319 ms 4416 KB Output is correct
18 Correct 317 ms 4228 KB Output is correct
19 Correct 370 ms 4684 KB Output is correct
20 Correct 337 ms 4792 KB Output is correct
21 Correct 328 ms 4508 KB Output is correct
22 Correct 326 ms 4228 KB Output is correct
23 Correct 358 ms 4748 KB Output is correct
24 Correct 362 ms 4724 KB Output is correct
25 Correct 339 ms 4488 KB Output is correct
26 Correct 344 ms 4348 KB Output is correct
27 Correct 366 ms 4860 KB Output is correct
28 Correct 366 ms 4724 KB Output is correct
29 Correct 360 ms 4616 KB Output is correct
30 Correct 354 ms 4340 KB Output is correct
31 Correct 383 ms 4868 KB Output is correct
32 Correct 386 ms 4980 KB Output is correct
33 Correct 374 ms 4716 KB Output is correct
34 Correct 377 ms 4468 KB Output is correct
35 Correct 406 ms 4916 KB Output is correct
36 Correct 402 ms 4980 KB Output is correct
37 Correct 390 ms 4740 KB Output is correct
38 Correct 388 ms 4404 KB Output is correct