Submission #805962

#	Time	Username	Problem	Language	Result	Execution time	Memory
805962		pavement	The Collection Game (BOI21_swaps)	C++17	25 / 100	24 ms	512 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
#define eb emplace_back

using ii = pair<int, int>;

int N, n0;
vector<ii> cmps;

void cmp(int x, int y) {
	if (x >= N || y >= N) return;
	cmps.eb(x, y);
}

void merge(vector<int> v) {
	if (v.size() == 2) {
		cmp(v[0], v[1]);
		return;
	}
	vector<int> even, odd;
	for (int i = 0; i < (int)v.size(); i++) {
		if (i % 2 == 0) even.pb(v[i]);
		else odd.pb(v[i]);
	}
	merge(even);
	merge(odd);
	for (int i = 1; i + 1 < (int)v.size(); i += 2) {
		cmp(v[i], v[i + 1]);
	}
}

void sort(vector<int> v) {
	if (v.size() == 2) {
		cmp(v[0], v[1]);
		return;
	}
	int m = (int)v.size() / 2;
	sort(vector<int>(v.begin(), v.begin() + m));
	sort(vector<int>(v.begin() + m, v.end()));
	merge(v);
}

void solve(int N, int V) {
	::N = N;
	n0 = 1;
	while (n0 < N) {
		n0 <<= 1;
	}
	vector<int> tmp;
	for (int i = 0; i < n0; i++) {
		tmp.pb(i);
	}
	sort(tmp);
	vector<int> Q, x, y;
	set<int> ss;
	for (int i = 1; i <= N; i++) {
		Q.pb(i - 1);
	}
	for (auto [a, b] : cmps) {
		if (ss.find(Q[a] + 1) != ss.end() || ss.find(Q[b] + 1) != 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(Q[a] + 1);
		ss.insert(Q[b] + 1);
		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: 0 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 0 / 9
• Subtask 5-2: 0 / 6
• Subtask 6-1: 0 / 21
• Subtask 6-2: 0 / 14
• Subtask 7-1: 0 / 9
• Subtask 7-2: 0 / 6