oj.uz

Submission #805960

# Submission time Handle Problem Language Result Execution time Memory
805960 2023-08-04T03:26:06 Z pavement The Collection Game (BOI21_swaps) C++17
100 / 100
 7 ms 576 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;
	set<int> ss;
	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;
						if (ss.find(a) != ss.end() || ss.find(b) != ss.end()) {
							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();
							ss.clear();
						}
						x.pb(a);
						y.pb(b);
						ss.insert(a);
						ss.insert(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]]);
		}
	}
	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 2 ms 288 KB Correct
3 Correct 3 ms 208 KB Correct
4 Correct 4 ms 332 KB Correct
5 Correct 5 ms 332 KB Correct
6 Correct 4 ms 332 KB Correct
7 Correct 6 ms 336 KB Correct
8 Correct 5 ms 328 KB Correct

Subtask #2
10.0 / 10.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 316 KB Correct
4 Correct 5 ms 336 KB Correct
5 Correct 5 ms 344 KB Correct
6 Correct 6 ms 576 KB Correct
7 Correct 5 ms 332 KB Correct
8 Correct 5 ms 332 KB Correct
9 Correct 7 ms 384 KB Correct
10 Correct 5 ms 336 KB Correct
11 Correct 4 ms 332 KB Correct
12 Correct 5 ms 332 KB Correct
13 Correct 4 ms 332 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 1 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 1 ms 268 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 328 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 268 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 328 KB Correct
5 Correct 1 ms 208 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 2 ms 320 KB Correct
8 Correct 6 ms 336 KB Correct
9 Correct 6 ms 336 KB Correct
10 Correct 6 ms 332 KB Correct
11 Correct 7 ms 332 KB Correct
12 Correct 4 ms 328 KB Correct
13 Correct 0 ms 208 KB Correct
14 Correct 1 ms 208 KB Correct
15 Correct 2 ms 308 KB Correct
16 Correct 7 ms 292 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 3 ms 208 KB Correct
4 Correct 4 ms 332 KB Correct
5 Correct 5 ms 344 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 3 ms 208 KB Correct
4 Correct 4 ms 332 KB Correct
5 Correct 5 ms 344 KB Correct
6 Correct 0 ms 208 KB Correct
7 Correct 1 ms 208 KB Correct
8 Correct 2 ms 312 KB Correct
9 Correct 6 ms 328 KB Correct
10 Correct 6 ms 340 KB Correct
11 Correct 5 ms 332 KB Correct
12 Correct 4 ms 328 KB Correct
13 Correct 5 ms 332 KB Correct
14 Correct 5 ms 332 KB Correct
15 Correct 5 ms 428 KB Correct
16 Correct 5 ms 324 KB Correct
17 Correct 4 ms 336 KB Correct
18 Correct 5 ms 328 KB Correct
19 Correct 0 ms 208 KB Correct
20 Correct 1 ms 208 KB Correct
21 Correct 3 ms 208 KB Correct
22 Correct 6 ms 344 KB Correct
23 Correct 5 ms 316 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 208 KB Correct
3 Correct 3 ms 312 KB Correct
4 Correct 6 ms 448 KB Correct
5 Correct 6 ms 288 KB Correct
6 Correct 4 ms 312 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 208 KB Correct
3 Correct 3 ms 312 KB Correct
4 Correct 6 ms 448 KB Correct
5 Correct 6 ms 288 KB Correct
6 Correct 4 ms 312 KB Correct
7 Correct 0 ms 208 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 2 ms 208 KB Correct
10 Correct 6 ms 332 KB Correct
11 Correct 6 ms 332 KB Correct
12 Correct 5 ms 332 KB Correct
13 Correct 6 ms 332 KB Correct
14 Correct 5 ms 328 KB Correct
15 Correct 5 ms 328 KB Correct
16 Correct 5 ms 328 KB Correct
17 Correct 4 ms 332 KB Correct
18 Correct 5 ms 332 KB Correct
19 Correct 4 ms 328 KB Correct
20 Correct 0 ms 208 KB Correct
21 Correct 1 ms 208 KB Correct
22 Correct 3 ms 316 KB Correct
23 Correct 5 ms 440 KB Correct
24 Correct 5 ms 332 KB Correct
25 Correct 7 ms 316 KB Correct

Subtask #7-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 208 KB Correct
4 Correct 4 ms 444 KB Correct
5 Correct 4 ms 328 KB Correct
6 Correct 4 ms 324 KB Correct
7 Correct 5 ms 312 KB Correct

Subtask #7-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 208 KB Correct
4 Correct 4 ms 444 KB Correct
5 Correct 4 ms 328 KB Correct
6 Correct 4 ms 324 KB Correct
7 Correct 5 ms 312 KB Correct
8 Correct 0 ms 208 KB Correct
9 Correct 0 ms 208 KB Correct
10 Correct 1 ms 208 KB Correct
11 Correct 2 ms 208 KB Correct
12 Correct 4 ms 332 KB Correct
13 Correct 5 ms 332 KB Correct
14 Correct 4 ms 332 KB Correct
15 Correct 5 ms 332 KB Correct
16 Correct 4 ms 340 KB Correct
17 Correct 5 ms 332 KB Correct
18 Correct 4 ms 332 KB Correct
19 Correct 6 ms 332 KB Correct
20 Correct 6 ms 328 KB Correct
21 Correct 5 ms 336 KB Correct
22 Correct 0 ms 208 KB Correct
23 Correct 1 ms 208 KB Correct
24 Correct 2 ms 208 KB Correct
25 Correct 4 ms 340 KB Correct
26 Correct 6 ms 332 KB Correct
27 Correct 5 ms 320 KB Correct
28 Correct 5 ms 284 KB Correct