Submission #1040249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040249		lovrot	Mechanical Doll (IOI18_doll)	C++17	100 / 100	88 ms	17784 KiB

doll

#include "doll.h"
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...) printf("")

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, int*> pip;

const int N = 2e5 + 10;

int n, m;

int cnt = 0, cntl, rgt[2 * N], lft[2 * N];
vector<int> C, X, Y;
vector<pip> p;

int rec(int k, int l) {
	int u = cnt++, siz = 1 << l;

	if(siz == 2) { 
		if(k == 2) { p.PB({cntl++, &lft[u]}); }
		p.PB({cntl++, &rgt[u]});
		return u; 
	}

	if(k <= siz / 2) { 
		lft[u] = -1;
	} else { 
		lft[u] = -(rec(k - siz / 2, l - 1) + 1);
	}
	rgt[u] = -(rec(min(k, siz / 2), l - 1) + 1);

	return u;
}

void create_circuit(int mm, vector<int> niz) {

	niz.PB(0);
	n = niz.size();
	m = mm;	
	
	C.resize(m + 1, -1);
	memset(rgt, -1, sizeof(rgt));
	memset(lft, -1, sizeof(lft));

	if(niz.size() & 1) { 
		C[0] = niz[0];
		niz.erase(niz.begin());
		--n;
	}

	int lg = 0;
	for(; (1 << lg) < n; ++lg);

	cntl = (1 << lg) - n;	
	rec(n, lg);

	sort(p.begin(), p.end(), [&lg](pip a, pip b) { 
		for(int i = 0; i <= lg; ++i) { 
			if((a.X & (1 << i)) != (b.X & (1 << i))) {
					return b.X & (1 << i);
			}
		}
		return 0;
	});

	for(int i = 0; i < n; ++i) { 
		*p[i].Y = niz[i];
	}

	X.resize(cnt);
	Y.resize(cnt);
	for(int i = 0; i < cnt; ++i) { 
		X[i] = lft[i];
		Y[i] = rgt[i];
	}

//	for(int i = 0; i < cnt; ++i) { 
//		debug("%d : %d %d\n", -(i + 1), X[i], Y[i]);
//	}
//	for(int i = 0; i < m + 1; ++i) { 
//		debug("%d %d\n", i, C[i]);
//	}

	//debug("bla\n");

	answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56