oj.uz

Submission #544807

# Submission time Handle Problem Language Result Execution time Memory
544807 2022-04-02T18:33:38 Z skittles1412 The Collection Game (BOI21_swaps) C++17
5 / 100
 4 ms 464 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 = 505, 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[512];
	iota(begin(tmp), end(tmp), 0);
	for (int i = 2; i < 512; i *= 2) {
		for (int j = 0; j < 512; 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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 3 ms 336 KB Correct
4 Incorrect 4 ms 396 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 2 ms 336 KB Correct
4 Incorrect 4 ms 396 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #3
3.0 / 3.0

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

Subtask #4
2.0 / 2.0

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

Subtask #5
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 376 KB Correct
4 Incorrect 4 ms 392 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #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 376 KB Correct
4 Incorrect 4 ms 392 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #7
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 2 ms 336 KB Correct
4 Incorrect 4 ms 336 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #8
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 2 ms 336 KB Correct
4 Incorrect 4 ms 336 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #9
0 / 21.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 Incorrect 3 ms 396 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 14.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 Incorrect 3 ms 396 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 2 ms 336 KB Correct
4 Incorrect 4 ms 392 KB Not correct
5 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Correct
2 Correct 2 ms 336 KB Correct
3 Correct 2 ms 336 KB Correct
4 Incorrect 4 ms 392 KB Not correct
5 Halted 0 ms 0 KB -