Submission #255254

#	Time	Username	Problem	Language	Result	Execution time	Memory
255254		arayi	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	155 ms	18360 KiB

doll

#include "doll.h"
//Arayi
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>

#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int> 
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;


const int N = 3e5 + 30;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 238;
const ld e = 1e-13;

int n, m, i1 = 1;
vii fp[N];
vii c, x, y;
bool col[N];
void rec(int ii, int v)
{
	if (!col[v])
	{
		col[v] = true;
		if (x[v] == mod)
		{
			x[v] = fp[ii].back();
			fp[ii].pop_back();
			rec(ii, -c[ii] - 1);
		}
		else if (x[v] < 0) rec(ii, -x[v] - 1);
	}
	else
	{
		col[v] = false;
		if (y[v] == mod)
		{
			y[v] = fp[ii].back();
			fp[ii].pop_back();
			rec(ii, -c[ii] - 1);
		}
		else if (y[v] < 0) rec(ii, -y[v] - 1);
	}
}
void mk(int ii)
{
	vii sm = fp[ii];
	int n = sm.size();
	int er = 0;
	while ((1 << er) < n) er++;
	int ss = (1 << er) - n;
	c[ii] = -i1;
	vii nax, nw;
	nax.ad(i1);
	i1++;
	x.ad(mod), y.ad(mod);
	for (int i = 1; i < er; i++)
	{
		for (int j = nax.size() - 1; j >= 0; j--)
		{
			nw.ad(i1);
			y[nax[j] - 1] = -i1, i1++;
			nw.ad(i1);
			x[nax[j] - 1] = -i1, i1++;
			x.ad(mod), x.ad(mod), y.ad(mod), y.ad(mod);
		}
		if (ss & (1 << (er - i)))
		{
			x[nax[0] - 1] = c[ii];
			i1--;
			x.pop_back();
			y.pop_back();
			nw.pop_back();
		}
		reverse(all(nw));
		swap(nax, nw);
		nw.clear();
	}
	if (ss & 1)
	{
		x[nax[0] - 1] = c[ii];
	}
	reverse(all(fp[ii]));
	rec(ii, -c[ii] - 1);
}
void create_circuit(int M, vector<int> A) {
	n = A.size();
	m = M;
	c.resize(m + 1);
	c[0] = A[0];
	for (int i = 0; i < n - 1; i++)
	{
		fp[A[i]].ad(A[i + 1]);
	}
	fp[A[n - 1]].ad(0);
	for (int i = 1; i <= m; i++)
	{
		if (fp[i].size() == 0) c[i] = 0;
		else if (fp[i].size() == 1) c[i] = fp[i].back();
		else mk(i);
	}
	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: 41.5530038336 / 56