제출 #1311020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311020		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<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==1) {
				network[depth].push_back({l,r});
				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;
	}
}

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

• 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