Submission #427983

#	Time	Username	Problem	Language	Result	Execution time	Memory
427983		patrikpavic2	The Collection Game (BOI21_swaps)	C++17	100 / 100	8 ms	508 KiB

swaps

#include "swaps.h"
#include <vector>
#include <algorithm>
#include <cstdio>

#define X first
#define Y second
#define PB push_back
#define EB emplace_back

using namespace std;

typedef vector < int > vi;
typedef pair < int, int > pii;

void solve(int n, int v) {
	int lg2 = 8;
	vector < int > P;
	vector < pii > tko;
	for(int i = 1;i <= n;i++) P.PB(i);
	for(int i = 0;i <= lg2;i++){
		for(int j = i;j >= 0;j--){
			for(int k = 0;k < n;k++){
				if(i != j && (k & (1 << j))){
					tko.EB(k ^ (1 << j), k);
					schedule(P[tko.back().X], P[tko.back().Y]);
				}
				if(i == j && (k ^ ((1 << (j + 1)) - 1)) < k){
					tko.EB(k ^ ((1 << (j + 1)) - 1), k);
					schedule(P[tko.back().X], P[tko.back().Y]);
				}	
			}
			vi odg = visit();
			for(int i = 0;i < (int)odg.size();i++)
				if(!odg[i]) swap(P[tko[i].X], P[tko[i].Y]);
			tko.clear();	
		}
	}
	answer(P);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 9 / 9
• Subtask 8: 6 / 6
• Subtask 9: 21 / 21
• Subtask 10: 14 / 14
• Subtask 11: 9 / 9
• Subtask 12: 6 / 6