Submission #138981

#	Time	Username	Problem	Language	Result	Execution time	Memory
138981		ckodser	Mechanical Doll (IOI18_doll)	C++14	53 / 100	241 ms	30860 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];
		
void bild(ll node,vector<ll> a){
	if(a.size()%2==1){
		a.pb(node);
		for(ll i=a.size()-2;i>=0;i--){
			swap(a[i],a[i+1]);
		}
	}
	if(a.size()==2){
		outx[-node]=a[0];
		outy[-node]=a[1];
		return;
	}
	outx[-node]=cnt--;
	outy[-node]=cnt--;
	vector<ll> l,r;
	for(ll i=0;i<a.size();i++){
		if(i&1){
			r.pb(a[i]);
		}else{
			l.pb(a[i]);
		}
	}
	bild(outx[-node],l);
	bild(outy[-node],r);
}
vector<ll> koj[maxn];
bool vis[maxn];
void create_circuit(int m,vector<int> a){
	a.pb(0);
	ll n=a.size();
	koj[0].pb(a[0]);
	for(ll i=0;i+1<n;i++){
		koj[a[i]].pb(a[i+1]);
	}
	vector<ll> c,x,y;
	c.resize(m+1);
	for(ll i=0;i<n;i++){
		ll v=a[i];
		if(koj[v].size()==1){
			c[v]=koj[v][0];
		}else{
			if(c[v]==0){
				c[v]=cnt--;
			}
		}
	}
	for(ll i=0;i<n;i++){
		ll v=a[i];
		if(!vis[v]){
			vis[v]=1;
			if(koj[v].size()>1){
				bild(c[v],koj[v]);
			}
		}
	}
	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 'void bild(int, std::vector<int>)':
doll.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(ll i=0;i<a.size();i++){
      |             ~^~~~~~~~~

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