Submission #426354

#	Time	Username	Problem	Language	Result	Execution time	Memory
426354		Pbezz	Mechanical Doll (IOI18_doll)	C++14	15 / 100	151 ms	12452 KiB

doll

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

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

void create_circuit(int M, std::vector<int> A) {
	int n = A.size(),k,S=-1,i,j,bruh;

	vector<vector<int>>adj(M+5);
	std::vector<int> X, Y;
	std::vector<int> C(M + 1);
	C[0]=A[0];
	for(i=0;i<n-1;i++){
	//C[A[i]]=A[i+1];
	adj[A[i]].pb(A[i+1]);
}
	adj[A[n-1]].pb(0);

	for(i=1;i<=M;i++){
	k=adj[i].size(); S=-(X.size())-1;
//	cout<<i<<" #"<<k<<endl;
	if(k==1){
	C[i]=adj[i][0];
	}else if(k>=2){

	ll cur=1,mock=1; bruh=0;
	C[i] = S;
	while(cur<k){//new level com cur switches
//	cout<<cur<<"jj\n";
	for(j=0;j<cur;j++){

	if(2*cur<k){//ainda vai haver next
	X.pb(-(2*mock));
	Y.pb(-(2*mock+1));//cout<<-(2*mock)-1<<" "<<-(2*mock+1)-1<<endl;
	}else{

	ll a=mock,siga=0,po=bruh;
	while(po>0){po--;
	if(a&(1LL<<0))siga|=(1LL<<po);
	a/=2;
	}
	//cout<<siga<<" "<<cur<<endl;
	if(siga<k){
	X.pb(adj[i][siga]);
	}else{
	X.pb(C[i]);
	}
	if(siga+cur<k-1){
	Y.pb(adj[i][siga+cur]);
	}else if(siga+cur==2*cur-1){
	Y.pb(adj[i][k-1]);
	}else{
	Y.pb(C[i]);
	}

	}

	mock++;
	}


cur*=2;bruh++;
}
}


}
/*
	for(i=0;i<=M;i++)cout<<C[i]<<" ";
	cout<<endl;

	for(auto u:X)cout<<u<<" ";
	cout<<endl;
	for(auto u:Y)cout<<u<<" ";
	cout<<endl;
*/

	
  answer(C, X, Y);
}

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