Submission #259848

#	Time	Username	Problem	Language	Result	Execution time	Memory
259848		medk	Mechanical Doll (IOI18_doll)	C++14	0 / 100	2 ms	204 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

vector<int> seq,X,Y,C;
int sz,dpth,layer;

void dfs(int u, int d, int v){
	if(d<dpth){
		dfs(u*2,d+1,v);
		dfs(u*2+1,d+1,v+(1<<(d-1)));
		X[u-1]=-u*2; Y[u-1]=X[u-1]-1;
		//cout<<u<<" "<<X[u-1]<<' '<<Y[u-1]<<endl;
	}
	else{
		X[u-1]=(v>=sz-1?-1:seq[v]);
		if(v+(1<<(d-1))==(1<<dpth)-1) Y[u-1]=0;
		else Y[u-1]=(v+(1<<(d-1))>=sz-1?-1:seq[v+(1<<(d-1))]);
		//cout<<u<<" "<<X[u-1]<<' '<<Y[u-1]<<endl;
	}
}

void create_circuit(int M, vector<int> A){
	seq=A;
	sz=sz(seq)+1;
	dpth=ceil(log2(sz));
	layer=(1<<dpth)-1;
	X.resize(layer), Y.resize(layer), C.resize(M+1);
	dfs(1,1,0);
	for(int i=0;i<=M;i++) C[i]=0;
	answer(C,X,Y);
}
/*
int main(){
	int m,n; cin>>m>>n;
	vector<int> tmp(n);
	for(int i=0;i<n;i++) cin>>tmp[i];
	create_circuit(m,tmp);
}*/

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