Submission #805960

#	Time	Username	Problem	Language	Result	Execution time	Memory
805960		pavement	The Collection Game (BOI21_swaps)	C++17	100 / 100	7 ms	576 KiB

swaps

//
// --- 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 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 9 / 9
• Subtask 5-2: 6 / 6
• Subtask 6-1: 21 / 21
• Subtask 6-2: 14 / 14
• Subtask 7-1: 9 / 9
• Subtask 7-2: 6 / 6