Submission #528512

#	Time	Username	Problem	Language	Result	Execution time	Memory
528512		fatemetmhr	The Collection Game (BOI21_swaps)	C++17	35 / 100	111 ms	47504 KiB

swaps

//    Be name khoda!

// --- 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 <bits/stdc++.h>


using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

const int maxn5 = 1e6 + 10;
const int maxnt = 1e6 + 10;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x)  x.begin(), x.end()

// schedule(i, j) -> (i > j)
// visit()
// answer(vector)

int n, mxlev = 0;
int anss[maxn5];
int lc[maxn5], rc[maxn5];
int root[maxnt], r1[maxnt], r2[maxnt];
int pt = 0;
int lev[maxnt], ver1[maxn5], ver2[maxn5];
int per[maxn5];
vector <int> ver, out, st[maxnt];
int lim = 5000;

inline void visitt(){
	lim--;
	if(lim < 0) exit(0);
	vector <int> res = visit();
	for(int j = 0; j < res.size(); j++)
		anss[ver1[j]] = anss[ver2[j]] = (res[j] ^ 1);
	pt = 0;
	return;
}

inline void solve(int l, int r, int v){
	mxlev = max(mxlev, lev[v]);
	if(r - l == 1){
		root[v] = r2[v] = l;
		r1[v] = -1;
		return;
	}
	int mid = (l + r) >> 1;
	lev[v * 2] = lev[v * 2 + 1] = lev[v] + 1;
	solve(l, mid, v * 2);
	solve(mid, r, v * 2 + 1);
	return;
}

inline void askk(int a, int b){
	ver1[pt] = a;
	ver2[pt] = b;
	pt++;
	schedule(per[a], per[b]);
	return;
}

inline pair<int, int> make_tree(int u, int v, bool ty = false){
	if(u == -1 || v == -1){
		if(ty)
			return {max(u, v), -1};
		return {-1, max(u, v)};
	}
	pair <int, int> rl = make_tree(lc[u], lc[v], false);
	pair <int, int> rr = make_tree(rc[u], rc[v], true);
	if(anss[u]) swap(u, v);
	lc[u] = rl.fi;
	lc[v] = rl.se;
	rc[u] = rr.fi;
	rc[v] = rr.se;
	return {u, v};
}

inline void sch(int u, int v){
	if(u == -1 || v == -1)
		return;
	askk(u, v);
	sch(lc[u], lc[v]);
	sch(rc[u], rc[v]);
	return;
}

inline void find_output(int r){
	if(r == -1)
		return;
	find_output(lc[r]);
	out.pb(per[r]);
	find_output(rc[r]);
	return;
}

void solve(int N, int V) {
	n = N;
	memset(lc, -1, sizeof lc);
	memset(rc, -1, sizeof rc);
	memset(r1, -1, sizeof r1);
	memset(r2, -1, sizeof r2);
	memset(lev, -1, sizeof lev);
	memset(root, -1, sizeof root);
	for(int i = 0; i < n; i++)
		per[i] = i + 1;
	shuffle(per, per + n, rng);
	
	lev[1] = 0;
	solve(0, n, 1);
	
	for(int i = mxlev; i >= 0; i--){
		ver.clear();
		for(int j = 1; j < maxnt; j++) if(lev[j] == i){
			ver.pb(j);
			st[j].clear();
			if(max(r1[j], r2[j]) == -1){
				r1[j] = root[j * 2];
				r2[j] = root[j * 2 + 1];
			}
			//cout << "ok " << j << ' ' << r1[j] << ' ' << r2[j] << endl;
		}
		
		bool ch = true;
		while(ch){
			//cout << "running " << endl;
			ch = false;
			for(auto v : ver) if(max(r1[v], r2[v]) > -1){
				if(min(r1[v], r2[v]) == -1){
					continue;
				}
				sch(r1[v], r2[v]);
				ch = true;
			}
			
			if(ch) visitt();
				
			for(auto v : ver) if(max(r1[v], r2[v]) > -1){
				if(min(r1[v], r2[v]) == -1){
					st[v].pb(max(r1[v], r2[v]));
					//cout << "* " << v << ' ' << st[v].size() << endl;
					r1[v] = r2[v] = -1;
					continue;
				}
				pair<int, int> r = make_tree(r1[v], r2[v]);
				r1[v] = r.fi; r2[v] = lc[r.se];
				st[v].pb(r.se);
				//cout << "& " << v << ' ' << st[v].size() << endl;
			}
		}
		for(auto v : ver){
			//cout << "aha " << v << ' ' << st[v].back() << ' ' << st[v].size() << endl;
			while(!st[v].empty()){
				int u = st[v].back();
				st[v].pop_back();
				if(st[v].size())
					lc[st[v].back()] = u;
				else
					root[v] = u;
			}
			//cout << root[v] << endl;
		}
	}
	
	
	find_output(root[1]); // remember to get per
	
	answer(out);
}

Compilation message (stderr)

swaps.cpp: In function 'void visitt()':
swaps.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int j = 0; j < res.size(); j++)
      |                 ~~^~~~~~~~~~~~

• 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: 0 / 9
• Subtask 8: 0 / 6
• Subtask 9: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6