oj.uz

Submission #674274

# Submission time Handle Problem Language Result Execution time Memory
674274 2022-12-23T15:55:54 Z rainboy Minerals (JOI19_minerals) C++17
75 / 100
 31 ms 2540 KB 
#include "minerals.h"

const int N = 43000, L = 16;

int k;

int Query_(int i) {
	int k_ = Query(i + 1);
	if (k_ == k)
		return 0;
	k = k_;
	return 1;
}

int tt[N * 2], ii[2][N], ii_[1 << L], nn[2], aa[N], bb[N];

void Solve(int n) {
	k = 0;
	for (int i = 0; i < n * 2; i++) {
		tt[i] = !Query_(i);
		ii[tt[i]][nn[tt[i]]++] = i;
	}
	for (int i = 0; i < n; i++) {
		int a = 0, c = 1;
		for (int l = 0; l < L; l++) {
			if ((i & 1 << l) != 0)
				c ^= 1;
			if (c)
				a |= 1 << l;
		}
		aa[i] = a;
	}
	for (int l = 0; l < L; l++) {
		for (int i = 0; i < n; i++)
			if ((aa[i] >> l & 1) != (l == 0 ? 1 : (aa[i] >> l - 1 & 1)))
				Query_(ii[0][i]);
		for (int i = 0; i < n; i++)
			if (!Query_(ii[1][i]))
				bb[i] |= 1 << l;
	}
	for (int i = 0; i < n; i++)
		ii_[aa[i]] = ii[0][i];
	for (int i = 0; i < n; i++)
		Answer(ii_[bb[i]] + 1, ii[1][i] + 1);
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:35:54: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   35 |    if ((aa[i] >> l & 1) != (l == 0 ? 1 : (aa[i] >> l - 1 & 1)))
      |                                                    ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 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 1 ms 348 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 5 ms 720 KB Output is correct
5 Correct 8 ms 1072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct
15 Correct 29 ms 2492 KB Output is correct
16 Correct 27 ms 2504 KB Output is correct
17 Correct 22 ms 2500 KB Output is correct
18 Correct 23 ms 2296 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct
15 Correct 29 ms 2492 KB Output is correct
16 Correct 27 ms 2504 KB Output is correct
17 Correct 22 ms 2500 KB Output is correct
18 Correct 23 ms 2296 KB Output is correct
19 Correct 31 ms 2504 KB Output is correct
20 Correct 23 ms 2508 KB Output is correct
21 Correct 23 ms 2540 KB Output is correct
22 Correct 18 ms 2348 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct
15 Correct 29 ms 2492 KB Output is correct
16 Correct 27 ms 2504 KB Output is correct
17 Correct 22 ms 2500 KB Output is correct
18 Correct 23 ms 2296 KB Output is correct
19 Correct 31 ms 2504 KB Output is correct
20 Correct 23 ms 2508 KB Output is correct
21 Correct 23 ms 2540 KB Output is correct
22 Correct 18 ms 2348 KB Output is correct
23 Incorrect 28 ms 2128 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct
15 Correct 29 ms 2492 KB Output is correct
16 Correct 27 ms 2504 KB Output is correct
17 Correct 22 ms 2500 KB Output is correct
18 Correct 23 ms 2296 KB Output is correct
19 Correct 31 ms 2504 KB Output is correct
20 Correct 23 ms 2508 KB Output is correct
21 Correct 23 ms 2540 KB Output is correct
22 Correct 18 ms 2348 KB Output is correct
23 Incorrect 28 ms 2128 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct
15 Correct 29 ms 2492 KB Output is correct
16 Correct 27 ms 2504 KB Output is correct
17 Correct 22 ms 2500 KB Output is correct
18 Correct 23 ms 2296 KB Output is correct
19 Correct 31 ms 2504 KB Output is correct
20 Correct 23 ms 2508 KB Output is correct
21 Correct 23 ms 2540 KB Output is correct
22 Correct 18 ms 2348 KB Output is correct
23 Incorrect 28 ms 2128 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 8 ms 1072 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 892 KB Output is correct
12 Correct 9 ms 1096 KB Output is correct
13 Correct 7 ms 1104 KB Output is correct
14 Correct 7 ms 1072 KB Output is correct
15 Correct 29 ms 2492 KB Output is correct
16 Correct 27 ms 2504 KB Output is correct
17 Correct 22 ms 2500 KB Output is correct
18 Correct 23 ms 2296 KB Output is correct
19 Correct 31 ms 2504 KB Output is correct
20 Correct 23 ms 2508 KB Output is correct
21 Correct 23 ms 2540 KB Output is correct
22 Correct 18 ms 2348 KB Output is correct
23 Incorrect 28 ms 2128 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -