제출 #1311024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311024		vlomaczk	The Collection Game (BOI21_swaps)	C++20	0 / 100	1 ms	332 KiB

swaps

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "swaps.h"
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*vector<int> A;
vector<pair<int, int>> scheduled;
set<int> used;
void schedule(int a, int b) {
	pair<int, int> v = {a,b};
	if(used.find(v.first)!=used.end() || used.find(v.second)!=used.end()) {
		cout << "Reapeted number in schedule\n";
		exit(0);
	}
	used.insert(v.first);
	used.insert(v.second);
	scheduled.push_back(v);
	if(A[v.first] < A[v.second]) swap(A[v.first], A[v.second]);
}
void visit() {
	while(scheduled.size()) scheduled.pop_back();
	while(used.size()) used.erase(*used.begin());
}
vector<int> r;
void answer(vector<int> R) { r = R; } */

vector<vector<pair<int, int>>> network;

void merge(vector<int> v, int &depth) {
	if(v.size()==2) {
		network[depth].push_back({v[0], v[1]});
		return;
	}
	vector<int> odd, even;
	for(int i=0; i<v.size(); i+=2) odd.push_back(v[i]);
	for(int i=1; i<v.size(); i+=2) even.push_back(v[i]);
	int old_depth = depth;
	merge(odd, depth);
	depth = old_depth;
	merge(even, depth);
	depth++;
	for(int i=1; i+1<v.size(); i+=2) {
		network[depth].push_back({v[i], v[i+1]});
	}
}

void prepareOddEvenBatcherSortingNetwork(int N) {
	int base = ceil(log2(double(N)));
	int n = 1<<base;
	network.resize(base*base);
	int sajz = 2;
	int depth = 0;
	while(sajz <= n) {
		for(int l=0; l<n; l+=sajz) {
			int r = l+sajz-1;
			if(sajz==2) {
				network[depth].push_back({l,r});
				if(l+sajz >= n) depth++;
				continue;
			}
			vector<int> vals;
			for(int x=l; x<=r; ++x) vals.push_back(x);
			int old = depth;
			merge(vals, depth);
			if(l+sajz < n) depth = old;
		}
		sajz *= 2;
	}
	/*for(auto vec : network) {
		if(vec.empty()) continue;
		for(auto[a,b] : vec) cout << "(" << a << " " << b << ") ";
		cout << "\n";
	}*/
}

void solve(int N, int V) {
	prepareOddEvenBatcherSortingNetwork(N);
	for(auto vec : network) {
		if(vec.empty()) continue;
		for(auto[a,b] : vec) if(a+1<=N && b+1<=N) schedule(b+1,a+1);
		visit();
	}
	vector<int> id;
	for(int i=1; i<=N; ++i) id.push_back(i);
	answer(id);
}

/*int main() {
	int n;
	cin >> n;
	A.assign(n+1, 0);
	for(int i=1; i<=n; ++i) cin >> A[i];
	solve(n, 0);
	bool ok = 1;
	for(int i=0; i<n; ++i) if(r[i] != A[i+1]) ok = 0;
	if(ok) cout << "OK\n";
	else cout << "ANS\n";
	for(int i=1; i<=n; ++i) cout << A[i] << " "; cout << "\n";
}*/

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