oj.uz

Submission #805961

# Submission time Handle Problem Language Result Execution time Memory
805961 2023-08-04T03:29:37 Z pavement The Collection Game (BOI21_swaps) C++17
100 / 100
 4 ms 444 KB 
//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;

#define pb push_back

void solve(int N, int V) {
	vector<int> Q, x, y;
	for (int i = 1; i <= N; i++) {
		Q.pb(i - 1);
	}
	for (int p = 1; p < N; p <<= 1) {
		for (int k = p; k >= 1; k >>= 1) {
			for (int j = k % p; j <= N - 1 - k; j += (k << 1)) {
				for (int i = 0; i <= min(k - 1, N - j - k - 1); i++) {
					if ((i + j) / (p << 1) == (i + j + k) / (p << 1)) {
						int a = i + j, b = i + j + k;
						x.pb(a);
						y.pb(b);
						schedule(Q[a] + 1, Q[b] + 1);
					}
				}
			}
			auto ret = visit();
			for (int l = 0; l < (int)ret.size(); l++) {
				if (!ret[l]) {
					swap(Q[x[l]], Q[y[l]]);
				}
			}
			x.clear();
			y.clear();
		}
	}
	for (int &i : Q) i++;
	answer(Q);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 3 ms 312 KB Correct
5 Correct 4 ms 308 KB Correct
6 Correct 3 ms 308 KB Correct
7 Correct 3 ms 308 KB Correct
8 Correct 4 ms 312 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 208 KB Correct
4 Correct 3 ms 312 KB Correct
5 Correct 3 ms 432 KB Correct
6 Correct 3 ms 312 KB Correct
7 Correct 4 ms 308 KB Correct
8 Correct 3 ms 304 KB Correct
9 Correct 3 ms 316 KB Correct
10 Correct 3 ms 316 KB Correct
11 Correct 3 ms 304 KB Correct
12 Correct 3 ms 308 KB Correct
13 Correct 4 ms 316 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct

Subtask #3-2
2.0 / 2.0

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

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 308 KB Correct
4 Correct 3 ms 312 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 308 KB Correct
4 Correct 3 ms 312 KB Correct
5 Correct 1 ms 256 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 1 ms 304 KB Correct
8 Correct 3 ms 312 KB Correct
9 Correct 4 ms 316 KB Correct
10 Correct 3 ms 312 KB Correct
11 Correct 3 ms 308 KB Correct
12 Correct 3 ms 308 KB Correct
13 Correct 0 ms 208 KB Correct
14 Correct 1 ms 208 KB Correct
15 Correct 2 ms 208 KB Correct
16 Correct 4 ms 312 KB Correct

Subtask #5-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 304 KB Correct
4 Correct 3 ms 316 KB Correct
5 Correct 4 ms 312 KB Correct

Subtask #5-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 304 KB Correct
4 Correct 3 ms 316 KB Correct
5 Correct 4 ms 312 KB Correct
6 Correct 0 ms 208 KB Correct
7 Correct 1 ms 208 KB Correct
8 Correct 2 ms 208 KB Correct
9 Correct 3 ms 316 KB Correct
10 Correct 3 ms 304 KB Correct
11 Correct 4 ms 316 KB Correct
12 Correct 4 ms 312 KB Correct
13 Correct 4 ms 312 KB Correct
14 Correct 3 ms 304 KB Correct
15 Correct 4 ms 308 KB Correct
16 Correct 3 ms 308 KB Correct
17 Correct 3 ms 316 KB Correct
18 Correct 3 ms 432 KB Correct
19 Correct 1 ms 208 KB Correct
20 Correct 1 ms 208 KB Correct
21 Correct 1 ms 208 KB Correct
22 Correct 4 ms 312 KB Correct
23 Correct 3 ms 288 KB Correct

Subtask #6-1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 300 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 3 ms 308 KB Correct
5 Correct 3 ms 288 KB Correct
6 Correct 3 ms 268 KB Correct

Subtask #6-2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 300 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 3 ms 308 KB Correct
5 Correct 3 ms 288 KB Correct
6 Correct 3 ms 268 KB Correct
7 Correct 0 ms 208 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 2 ms 300 KB Correct
10 Correct 3 ms 308 KB Correct
11 Correct 4 ms 308 KB Correct
12 Correct 4 ms 316 KB Correct
13 Correct 4 ms 308 KB Correct
14 Correct 3 ms 312 KB Correct
15 Correct 3 ms 308 KB Correct
16 Correct 4 ms 312 KB Correct
17 Correct 4 ms 312 KB Correct
18 Correct 3 ms 320 KB Correct
19 Correct 3 ms 308 KB Correct
20 Correct 0 ms 208 KB Correct
21 Correct 1 ms 296 KB Correct
22 Correct 2 ms 208 KB Correct
23 Correct 3 ms 316 KB Correct
24 Correct 3 ms 316 KB Correct
25 Correct 3 ms 292 KB Correct

Subtask #7-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 300 KB Correct
4 Correct 3 ms 316 KB Correct
5 Correct 4 ms 300 KB Correct
6 Correct 3 ms 276 KB Correct
7 Correct 3 ms 272 KB Correct

Subtask #7-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 300 KB Correct
4 Correct 3 ms 316 KB Correct
5 Correct 4 ms 300 KB Correct
6 Correct 3 ms 276 KB Correct
7 Correct 3 ms 272 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 0 ms 208 KB Correct
10 Correct 1 ms 208 KB Correct
11 Correct 1 ms 208 KB Correct
12 Correct 4 ms 444 KB Correct
13 Correct 3 ms 312 KB Correct
14 Correct 4 ms 312 KB Correct
15 Correct 3 ms 308 KB Correct
16 Correct 3 ms 316 KB Correct
17 Correct 3 ms 312 KB Correct
18 Correct 3 ms 316 KB Correct
19 Correct 3 ms 308 KB Correct
20 Correct 4 ms 316 KB Correct
21 Correct 3 ms 340 KB Correct
22 Correct 0 ms 208 KB Correct
23 Correct 1 ms 208 KB Correct
24 Correct 2 ms 304 KB Correct
25 Correct 4 ms 312 KB Correct
26 Correct 3 ms 284 KB Correct
27 Correct 4 ms 268 KB Correct
28 Correct 3 ms 272 KB Correct