Submission #138985

#	Time	Username	Problem	Language	Result	Execution time	Memory
138985		ckodser	Mechanical Doll (IOI18_doll)	C++14	28 / 100	138 ms	11376 KiB

doll

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

#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=6e5+500;
const ll inf=1e9+900;
const ll mod=1e9+7;


ll cnt=-2;
ll outx[maxn];
ll outy[maxn];

bool yeki(vector<ll> vec){
	for(ll i=1;i<vec.size();i++)if(vec[i]!=vec[0])return 0;
	return 1;
}
void bild(ll node,vector<ll> a,ll sz,ll v){
	ll n=a.size();
	if(sz==2){
		if(n==1){
			outx[-node]=v;
			outy[-node]=a[0];
		}
		if(n==2){
			outx[-node]=a[0];
			outy[-node]=a[1];
		}
		return;
	}
	ll e=sz-n;
	if(e>=sz/2){
		e-=sz/2;
		outx[-node]=v;
		outy[-node]=cnt--;
		bild(outy[-node],a,sz/2,v);
		return ;
	}
	vector<ll> l,r;
	bool last=1;
	for(ll i=0;i<(ll)a.size();i++){
		if(last){
			if(e){
				e--;
				i--;
			}else{
				l.pb(a[i]);
			}
		}else{
			r.pb(a[i]);
		}
		last=(!last);
	}
	outx[-node]=cnt--;
	bild(outx[-node],l,sz/2,v);
	outy[-node]=cnt--;
	bild(outy[-node],r,sz/2,v);
}
void create_circuit(int m,vector<int> a){
	a.pb(0);
	ll n=a.size();
	vector<ll> c,x,y;
	c.resize(m+1);
	vector<ll> b;
	for(ll i=1;i<n;i++)b.pb(a[i]);
	fill(c.begin(),c.end(),-1);
	c[0]=a[0];
	ll v=b.size();
	while((v&(-v))!=v)v++;
	bild(-1,b,v,-1);
	for(ll i=-1;i>cnt;i--){
		x.pb(outx[-i]);
		y.pb(outy[-i]);
	}
	/*
	for(auto v:c)cout<<v<<' ';
	cout<<endl;
	for(auto v:x)cout<<v<<' ';
	cout<<endl;
	for(auto v:y)cout<<v<<' ';
	cout<<endl;
	*/
	answer(c,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'bool yeki(std::vector<int>)':
doll.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i=1;i<vec.size();i++)if(vec[i]!=vec[0])return 0;
      |             ~^~~~~~~~~~~

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