Submission #805914

#	Time	Username	Problem	Language	Result	Execution time	Memory
805914		pavement	The Collection Game (BOI21_swaps)	C++17	51 / 100	6 ms	344 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> P, x, y;
	set<int> ss;
	for (int i = 1; i <= N; i++) {
		P.pb(i);
	}
	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)) {
						if (ss.find(i + j + 1) != ss.end() || ss.find(i + j + k + 1) != ss.end()) {
							auto ret = visit();
							for (int l = 0; l < (int)ret.size(); l++) {
								if (!ret[l]) swap(P[x[l]], P[y[l]]);
							}
							x.clear();
							y.clear();
							ss.clear();
						}
						x.pb(i + j);
						y.pb(i + j + k);
						ss.insert(i + j + 1);
						ss.insert(i + j + k + 1);
						schedule(i + j + 1, i + j + k + 1);
					}
				}
			}
		}
	}
	auto ret = visit();
	for (int l = 0; l < (int)ret.size(); l++) {
		if (!ret[l]) swap(P[x[l]], P[y[l]]);
	}
	answer(P);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 0 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 0 / 6
• Subtask 5-1: 9 / 9
• Subtask 5-2: 0 / 6
• Subtask 6-1: 21 / 21
• Subtask 6-2: 0 / 14
• Subtask 7-1: 9 / 9
• Subtask 7-2: 0 / 6