Submission #1183692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183692		kl0989e	The Collection Game (BOI21_swaps)	C++20	100 / 100	2 ms	424 KiB

swaps

#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

vector<pi> ops;

void custom_schedule(int a, int b, int n) {
	ops.pb({a,b});
	if (a<=n && b<=n) {
		schedule(a,b);
	}
}

vi custom_visit(int n) {
	vi t=visit();
	vi ret;
	int pt=0;
	for (int i=0; i<ops.size(); i++) {
		if (ops[i].fi>n || ops[i].se>n) {
			ret.pb((-ops[i].fi) > (-ops[i].se));
		}
		else {
			ret.pb(t[pt++]);
		}
	}
	ops.clear();
	return ret;
}

void solve(int n, int v) {
	int m=n;
	while (__builtin_popcount(m)!=1) {
		m++;
	}
    vi ord(m);
    iota(all(ord),1);
	for (int k=2; k<=m; k*=2) {
		for (int j=k/2; j>0; j/=2) {
			for (int i=0; i<m; i++) {
				int l=i^j;
				if (l>i) {
					custom_schedule(ord[i],ord[l],n);
				}
			}
			vi temp=custom_visit(n);
			int pt=0;
			for (int i=0; i<m; i++) {
				int l=i^j;
				if (l>i) {
					if (((i&k)==0 && temp[pt]==0) || ((i&k)!=0 && temp[pt]==1)) {
						swap(ord[i],ord[l]);
					}
					pt++;
				}
			}
		}
	}
	while (ord.size()>n) {
		ord.pop_back();
	}
    answer(ord);
}

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