oj.uz

Submission #544809

# Submission time Handle Problem Language Result Execution time Memory
544809 2022-04-02T18:36:27 Z skittles1412 The Collection Game (BOI21_swaps) C++17
100 / 100
 7 ms 532 KB 
#include "bits/extc++.h"
#include "swaps.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 512, logn = 9;

namespace wrapper {

int perm[maxn];
vector<pair<int, int>> queued;

void init() {
	iota(begin(perm), end(perm), 1);
}

void mschedule(int a, int b) {
	queued.emplace_back(a, b);
}

void mvisit() {
	if (!sz(queued)) {
		return;
	}
	for (auto& [a, b] : queued) {
		schedule(perm[a], perm[b]);
	}
	vector<int> res = visit();
	int rind = 0;
	for (auto& [a, b] : queued) {
		if (!res[rind++]) {
			swap(perm[a], perm[b]);
		}
	}
	queued.clear();
}

void manswer(int n) {
	answer(vector<int>(perm, perm + n));
}

}  // namespace wrapper

int gind;
vector<pair<int, int>> swaps[logn][logn];

void merge(const vector<int>& arr, int d) {
	if (sz(arr) == 2) {
		swaps[gind][d].emplace_back(arr[0], arr[1]);
		return;
	}
	vector<int> nxt[2];
	for (int i = 0; i < sz(arr); i++) {
		nxt[i & 1].push_back(arr[i]);
	}
	merge(nxt[0], d + 1);
	merge(nxt[1], d + 1);
	for (int i = 1; i + 2 < sz(arr); i += 2) {
		swaps[gind][d].emplace_back(arr[i], arr[i + 1]);
	}
}

void solve(int n, int) {
	wrapper::init();
	int tmp[maxn];
	iota(begin(tmp), end(tmp), 0);
	for (int i = 2; i <= maxn; i *= 2) {
		for (int j = 0; j < maxn; j += i) {
			merge(vector<int>(tmp + j, tmp + j + i), 0);
		}
		gind++;
	}
	for (auto& a : swaps) {
		for (int i = logn - 1; i >= 0; i--) {
			if (sz(a[i])) {
				for (auto& [x, y] : a[i]) {
					if (x < n && y < n) {
						wrapper::mschedule(x, y);
					}
				}
				wrapper::mvisit();
			}
		}
	}
	wrapper::manswer(n);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 4 ms 336 KB Correct
4 Correct 4 ms 416 KB Correct
5 Correct 4 ms 404 KB Correct
6 Correct 5 ms 396 KB Correct
7 Correct 4 ms 408 KB Correct
8 Correct 4 ms 408 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 4 ms 336 KB Correct
4 Correct 5 ms 412 KB Correct
5 Correct 4 ms 408 KB Correct
6 Correct 4 ms 408 KB Correct
7 Correct 4 ms 388 KB Correct
8 Correct 6 ms 404 KB Correct
9 Correct 6 ms 408 KB Correct
10 Correct 4 ms 416 KB Correct
11 Correct 4 ms 416 KB Correct
12 Correct 4 ms 412 KB Correct
13 Correct 5 ms 408 KB Correct

Subtask #3
3.0 / 3.0

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

Subtask #4
2.0 / 2.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 5 ms 408 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 5 ms 408 KB Correct
5 Correct 2 ms 336 KB Correct
6 Correct 2 ms 336 KB Correct
7 Correct 3 ms 336 KB Correct
8 Correct 5 ms 408 KB Correct
9 Correct 4 ms 404 KB Correct
10 Correct 4 ms 416 KB Correct
11 Correct 4 ms 412 KB Correct
12 Correct 6 ms 408 KB Correct
13 Correct 1 ms 336 KB Correct
14 Correct 2 ms 336 KB Correct
15 Correct 3 ms 336 KB Correct
16 Correct 5 ms 412 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 3 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 4 ms 412 KB Correct
5 Correct 4 ms 408 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 3 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 4 ms 412 KB Correct
5 Correct 4 ms 408 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 2 ms 336 KB Correct
8 Correct 3 ms 336 KB Correct
9 Correct 4 ms 412 KB Correct
10 Correct 4 ms 412 KB Correct
11 Correct 4 ms 404 KB Correct
12 Correct 5 ms 416 KB Correct
13 Correct 6 ms 408 KB Correct
14 Correct 5 ms 412 KB Correct
15 Correct 4 ms 416 KB Correct
16 Correct 6 ms 412 KB Correct
17 Correct 5 ms 532 KB Correct
18 Correct 4 ms 408 KB Correct
19 Correct 1 ms 336 KB Correct
20 Correct 2 ms 336 KB Correct
21 Correct 3 ms 296 KB Correct
22 Correct 5 ms 408 KB Correct
23 Correct 5 ms 392 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 4 ms 412 KB Correct
5 Correct 4 ms 404 KB Correct
6 Correct 4 ms 396 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 4 ms 412 KB Correct
5 Correct 4 ms 404 KB Correct
6 Correct 4 ms 396 KB Correct
7 Correct 1 ms 380 KB Correct
8 Correct 2 ms 336 KB Correct
9 Correct 3 ms 336 KB Correct
10 Correct 5 ms 524 KB Correct
11 Correct 7 ms 408 KB Correct
12 Correct 6 ms 440 KB Correct
13 Correct 5 ms 408 KB Correct
14 Correct 7 ms 404 KB Correct
15 Correct 5 ms 412 KB Correct
16 Correct 5 ms 412 KB Correct
17 Correct 5 ms 408 KB Correct
18 Correct 4 ms 404 KB Correct
19 Correct 5 ms 408 KB Correct
20 Correct 1 ms 336 KB Correct
21 Correct 2 ms 336 KB Correct
22 Correct 4 ms 336 KB Correct
23 Correct 5 ms 404 KB Correct
24 Correct 6 ms 412 KB Correct
25 Correct 4 ms 392 KB Correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 4 ms 412 KB Correct
5 Correct 4 ms 388 KB Correct
6 Correct 4 ms 388 KB Correct
7 Correct 6 ms 388 KB Correct

Subtask #12
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Correct 4 ms 412 KB Correct
5 Correct 4 ms 388 KB Correct
6 Correct 4 ms 388 KB Correct
7 Correct 6 ms 388 KB Correct
8 Correct 1 ms 336 KB Correct
9 Correct 1 ms 336 KB Correct
10 Correct 2 ms 336 KB Correct
11 Correct 3 ms 336 KB Correct
12 Correct 4 ms 408 KB Correct
13 Correct 6 ms 416 KB Correct
14 Correct 4 ms 416 KB Correct
15 Correct 4 ms 408 KB Correct
16 Correct 6 ms 408 KB Correct
17 Correct 5 ms 412 KB Correct
18 Correct 4 ms 408 KB Correct
19 Correct 4 ms 412 KB Correct
20 Correct 7 ms 408 KB Correct
21 Correct 6 ms 412 KB Correct
22 Correct 1 ms 308 KB Correct
23 Correct 2 ms 336 KB Correct
24 Correct 3 ms 336 KB Correct
25 Correct 5 ms 412 KB Correct
26 Correct 4 ms 404 KB Correct
27 Correct 4 ms 392 KB Correct
28 Correct 5 ms 448 KB Correct