Submission #570430

#	Time	Username	Problem	Language	Result	Execution time	Memory
570430		PedroBigMan	Mechanical Doll (IOI18_doll)	C++14	100 / 100	161 ms	27880 KiB

doll

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "doll.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

void create_circuit(int M, vector<int> A) 
{
	ll N = A.size();
	ll L = N/2 +1;
	ll H = log2(2LL*L-1) +1; //depths 0,1,...,H-1
	ll T = 1LL<<H;
	vector<pl> S; VV(S,T,((pl){0,0}));
	vector<pl> range; VV(range,T,((pl) {-1,-1}));
	for(ll i=T-1;i>=1;i--) 
	{
		if(i>=T/2) {range[i]={i-T/2,i-T/2};}
		else {range[i]={range[2*i].ff,range[2*i].ss};}
	}
	REP(i,1,T)
	{
		if(range[i].ff>=L && range[i/2].ff<L)
		{
			S[i/2].ss=S[i/2].ff;
			S[i/2].ff=1;
		}
		if(range[i].ff<L) {if(i>=T/2) {S[i]={1,1};} else{S[i]={2*i,2*i+1};}}
	}
	vector<ll> sw; VV(sw,T,0);
	vector<pl> order; 
	ll count=0;
	ll cur=1;
	while(count<=2)
	{
		if(cur==T/2) {count++; if(count==3) {break;}}
		if(cur>=T/2) {order.pb({cur,sw[cur]});}
		sw[cur]=(sw[cur]+1)%2;
		if(sw[cur]==0) {cur=S[cur].ss;} else {cur=S[cur].ff;}
	}
	REP(i,0,N) 
	{
		if(order[i].ss==0) {S[order[i].ff].ff=A[i];}
		else {S[order[i].ff].ss=A[i];}
	}
	REP(i,N,order.size())
	{
		if(i==order.size()-1)
		{
			if(order[i].ss==0) {S[order[i].ff].ff=0;}
			else {S[order[i].ff].ss=0;}	
		}
		else
		{
			if(order[i].ss==0) {S[order[i].ff].ff=-1;}
			else {S[order[i].ff].ss=-1;}	
		}
	}
	unordered_map<ll,ll> m; ll ind=1;
	vector<ll> Sw; Sw.pb(-1);
	REP(i,0,T)
	{
		if(S[i].ff==0 && S[i].ss==0) {m[i]=-1;}
		else {m[i]=ind; Sw.pb(i); ind++;}
	}
	vector<ll> C; REP(i,0,M+1) {C.pb(-1);}
	vector<ll> X,Y; VV(X,ind-1,-1); VV(Y,ind-1,-1);
	REP(i,1,ind)
	{
		if(Sw[i]>=T/2) 
		{
			X[i-1]=S[Sw[i]].ff;
			Y[i-1]=S[Sw[i]].ss;
		}
		else
		{
			X[i-1]=-m[S[Sw[i]].ff];
			Y[i-1]=-m[S[Sw[i]].ss];
		}
	}
	//REP(i,0,ind-1) {cout<<X[i]<<" "<<Y[i]<<endl;}
	answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
doll.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:89:7: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   if(i==order.size()-1)
      |      ~^~~~~~~~~~~~~~~~

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