Submission #82138

#	Time	Username	Problem	Language	Result	Execution time	Memory
82138		PowerOfNinjaGo	Mechanical Doll (IOI18_doll)	C++17	37 / 100	215 ms	16500 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int high;

const int maxn = 8e5+5;

int L[maxn], R[maxn];
vector<int> all, matter;

void build(int cur, int bit, int dep, int to)
{
	if(dep == high) 
	{
		if(bit) R[cur] = -to;
		else L[cur] = -to;
		return;
	}
	if(bit&1)
	{
		R[cur] = cur*2+1;
		build(cur*2+1, bit>>1, dep+1, to);
	}
	else
	{
		L[cur] = cur*2;
		build(cur*2, bit>>1, dep+1, to);
	}
}

bool cmp(int a, int b)
{
	for(int i = high; i>= 0; i--)
	{
		int x = a & (1<<i);
		int y = b & (1<<i);
		if(x != y) return x< y;
	}
}

void create_circuit(int m, vector<int> A)
{
	memset(L, 31, sizeof L);
	memset(R, 31, sizeof R);
	int n = A.size();
	int leaves = n;
	int sig = -1;
	for(int i = 20; i>= 0; i--)
	{
		if((1<<i) & leaves)
		{
			sig = i+1;
			break;
		}
	}
	high = sig;
	for(int i = 0; i< n; i++) all.pb(i);
	all.pb((1<<high)-1);
	sort(all.begin(), all.end(), cmp);
	for(int i = 0; i<= n; i++)
	{
		build(1, all[i], 1, i< n?A[i]:0); 
	}
	for(int i = 0; i< (1<<high); i++)
	{
		if(L[i]> 0 && L[i] != 522133279) matter.pb(L[i]);
		if(R[i]> 0 && R[i] != 522133279) matter.pb(R[i]);
	}
	matter.pb(1);
	sort(matter.begin(), matter.end());
	vector<int> ansx, ansy;
	ansx.resize(matter.size());
	ansy.resize(matter.size());
	vector<int> res(m+1, -1);
	for(int i = 0; i< (int) matter.size(); i++)
	{
		int sw = matter[i];
		if(L[sw]> 0)
		{
			if(L[sw] == 522133279) ansx[i] = -1;
			else ansx[i] = -(lower_bound(matter.begin(), matter.end(), L[sw])-matter.begin()+1);
		}
		else
		{
			ansx[i] = -L[sw];
		}
		if(R[sw]> 0)
		{
			if(R[sw] == 522133279) ansy[i] = -1;
			else ansy[i] = -(lower_bound(matter.begin(), matter.end(), R[sw])-matter.begin()+1);
		}
		else
		{
			ansy[i] = -R[sw];
		}
	}
	answer(res, ansx, ansy);
}

Compilation message (stderr)

doll.cpp: In function 'bool cmp(int, int)':
doll.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

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