oj.uz

Submission #838870

# Submission time Handle Problem Language Result Execution time Memory
838870 2023-08-28T03:12:42 Z pavement Minerals (JOI19_minerals) C++17
40 / 100
 20 ms 2896 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair

void Solve(int N) {
	vector<int> uniq, others;
	for (int i = 0, prv = 0; i < 2 * N; i++) {
		if (Query(i + 1) > prv) {
			uniq.pb(i);
			prv++;
		} else {
			others.pb(i);
		}
	}
	for (int i = 0; i < 2 * N; i++) {
		Query(i + 1);
	}
	vector<int> lo(2 * N, 0), hi(2 * N, N - 1), mid(2 * N), ans(2 * N, -1);
	int cur_l = -1, cur_r = -1;
	for (int rep = 0; (1 << rep) <= N; rep++) {
		vector<bool> can(2 * N, 0);
		for (int i : others) {
			mid[i] = (lo[i] + hi[i]) / 2;
			// insert [lo[i], mid[i]] from uniq
		}
		sort(others.begin(), others.end(), [&](const auto &lhs, const auto &rhs) {
			return mp(lo[lhs], mid[rhs]) < mp(lo[rhs], mid[rhs]);
		});
		for (int i : others) {
			if (cur_l == -1 || cur_l > lo[i]) {
				if (cur_l != -1) {
					for (int j = cur_l; j <= cur_r; j++) {
						Query(uniq[j] + 1);
					}
				}
				for (int j = lo[i]; j <= mid[i]; j++) {
					Query(uniq[j] + 1);
				}
				cur_l = lo[i];
				cur_r = mid[i];
			} else {
				if (cur_r > mid[i]) {
					for (int j = cur_r; j > mid[i]; j--) {
						Query(uniq[j] + 1);
					}
				} else {
					for (int j = cur_r + 1; j <= mid[i]; j++) {
						Query(uniq[j] + 1);
					}
				}
				cur_r = mid[i];
				assert(cur_l <= lo[i]);
				for (int j = cur_l; j < lo[i]; j++) {
					Query(uniq[j] + 1);
				}
				cur_l = lo[i];
			}
			int ret_1 = Query(i + 1);
			int ret_2 = Query(i + 1);
			if (ret_1 == ret_2) {
				can[i] = 1;
			}
		}
		for (int i : others) {
			if (can[i]) {
				ans[i] = mid[i];
				hi[i] = mid[i] - 1;
			} else {
				lo[i] = mid[i] + 1;
			}
		}
	}
	for (int i : others) {
		Answer(i + 1, uniq[ans[i]] + 1);
	}
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 7 ms 804 KB Output is correct
5 Correct 13 ms 1256 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct
15 Incorrect 20 ms 2896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct
15 Incorrect 20 ms 2896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct
15 Incorrect 20 ms 2896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct
15 Incorrect 20 ms 2896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct
15 Incorrect 20 ms 2896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 7 ms 804 KB Output is correct
9 Correct 13 ms 1256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 15 ms 1316 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1264 KB Output is correct
15 Incorrect 20 ms 2896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -