oj.uz

Submission #263585

# Submission time Handle Problem Language Result Execution time Memory
263585 2020-08-13T19:49:31 Z keko37 Minerals (JOI19_minerals) C++14
85 / 100
 73 ms 4124 KB 
#include<bits/stdc++.h>
#include "minerals.h"

using namespace std;

typedef vector <int> vi;

const int MAXN = 45000;

int n, prosli = 0;
int dp[MAXN], opt[MAXN];

int calc (int len) {
    if (dp[len] != -1) return dp[len];
    if (len == 1) return dp[len] = 0;
    int res = 1e9;
    int x = (double) len / 2.618;
    for (int j = 0; j <= 1; j++) {
        int i = x + j;
        if (i < 1 || i >= len) continue;
        int tmp = min(i, len - i) + len - 1 + calc(i) + calc(len - i);
        if (tmp < res) {
            res = tmp;
            opt[len] = i;
        }
    }
    return dp[len] = res;
}

bool pitaj (int x) {
	int novi = Query(x);
	bool res = (prosli != novi);
	prosli = novi;
	return res;
}

void calc (vi a, vi b, bool flg) {
	int siz = a.size();
	if (siz == 1) {
		Answer(a[0], b[0]);
		return;
	}
	int x = opt[siz];
	vi a1, b1, a2, b2;
	for (int i = 0; i < siz; i++) {
		if (i < x) {
			pitaj(a[i]);
			a1.push_back(a[i]);
		} else {
			a2.push_back(a[i]);
		}
	}
	for (int i = 0; i < siz; i++) {
		if (pitaj(b[i]) ^ flg) b2.push_back(b[i]); else b1.push_back(b[i]);
	}
	calc(a1, b1, !flg);
	calc(a2, b2, flg);
}

void init () {
	vi a, b;
	for (int i = 1; i <= 2 * n; i++) {
		if (pitaj(i)) a.push_back(i); else b.push_back(i);
	}
	calc(a, b, 1);
}

void Solve (int N) {
	n = N;
	memset(dp, -1, sizeof dp);
	calc(n);
	init();
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 13 ms 1252 KB Output is correct
5 Correct 26 ms 1788 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct
15 Correct 63 ms 3824 KB Output is correct
16 Correct 65 ms 3776 KB Output is correct
17 Correct 60 ms 3776 KB Output is correct
18 Correct 57 ms 3604 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct
15 Correct 63 ms 3824 KB Output is correct
16 Correct 65 ms 3776 KB Output is correct
17 Correct 60 ms 3776 KB Output is correct
18 Correct 57 ms 3604 KB Output is correct
19 Correct 61 ms 3832 KB Output is correct
20 Correct 68 ms 3876 KB Output is correct
21 Correct 58 ms 3828 KB Output is correct
22 Correct 60 ms 3656 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct
15 Correct 63 ms 3824 KB Output is correct
16 Correct 65 ms 3776 KB Output is correct
17 Correct 60 ms 3776 KB Output is correct
18 Correct 57 ms 3604 KB Output is correct
19 Correct 61 ms 3832 KB Output is correct
20 Correct 68 ms 3876 KB Output is correct
21 Correct 58 ms 3828 KB Output is correct
22 Correct 60 ms 3656 KB Output is correct
23 Correct 69 ms 3944 KB Output is correct
24 Correct 63 ms 4092 KB Output is correct
25 Correct 67 ms 3940 KB Output is correct
26 Correct 57 ms 3740 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct
15 Correct 63 ms 3824 KB Output is correct
16 Correct 65 ms 3776 KB Output is correct
17 Correct 60 ms 3776 KB Output is correct
18 Correct 57 ms 3604 KB Output is correct
19 Correct 61 ms 3832 KB Output is correct
20 Correct 68 ms 3876 KB Output is correct
21 Correct 58 ms 3828 KB Output is correct
22 Correct 60 ms 3656 KB Output is correct
23 Correct 69 ms 3944 KB Output is correct
24 Correct 63 ms 4092 KB Output is correct
25 Correct 67 ms 3940 KB Output is correct
26 Correct 57 ms 3740 KB Output is correct
27 Correct 66 ms 4044 KB Output is correct
28 Correct 69 ms 4024 KB Output is correct
29 Correct 73 ms 4032 KB Output is correct
30 Correct 71 ms 3844 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct
15 Correct 63 ms 3824 KB Output is correct
16 Correct 65 ms 3776 KB Output is correct
17 Correct 60 ms 3776 KB Output is correct
18 Correct 57 ms 3604 KB Output is correct
19 Correct 61 ms 3832 KB Output is correct
20 Correct 68 ms 3876 KB Output is correct
21 Correct 58 ms 3828 KB Output is correct
22 Correct 60 ms 3656 KB Output is correct
23 Correct 69 ms 3944 KB Output is correct
24 Correct 63 ms 4092 KB Output is correct
25 Correct 67 ms 3940 KB Output is correct
26 Correct 57 ms 3740 KB Output is correct
27 Correct 66 ms 4044 KB Output is correct
28 Correct 69 ms 4024 KB Output is correct
29 Correct 73 ms 4032 KB Output is correct
30 Correct 71 ms 3844 KB Output is correct
31 Incorrect 68 ms 4124 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1252 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 16 ms 1424 KB Output is correct
12 Correct 22 ms 1804 KB Output is correct
13 Correct 20 ms 1804 KB Output is correct
14 Correct 21 ms 1740 KB Output is correct
15 Correct 63 ms 3824 KB Output is correct
16 Correct 65 ms 3776 KB Output is correct
17 Correct 60 ms 3776 KB Output is correct
18 Correct 57 ms 3604 KB Output is correct
19 Correct 61 ms 3832 KB Output is correct
20 Correct 68 ms 3876 KB Output is correct
21 Correct 58 ms 3828 KB Output is correct
22 Correct 60 ms 3656 KB Output is correct
23 Correct 69 ms 3944 KB Output is correct
24 Correct 63 ms 4092 KB Output is correct
25 Correct 67 ms 3940 KB Output is correct
26 Correct 57 ms 3740 KB Output is correct
27 Correct 66 ms 4044 KB Output is correct
28 Correct 69 ms 4024 KB Output is correct
29 Correct 73 ms 4032 KB Output is correct
30 Correct 71 ms 3844 KB Output is correct
31 Incorrect 68 ms 4124 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -