Submission #418992

#	Time	Username	Problem	Language	Result	Execution time	Memory
418992		MeGustaElArroz23	Mechanical Doll (IOI18_doll)	C++14	53 / 100	165 ms	23908 KiB

doll

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;

#define deb(x) cerr << #x << " = " << x << ", ";
#define br cerr<<'\n';
#define debr(x) cerr << #x<<" = "<<x<<'\n';
void debv_(auto v){
  	for (int x:v) cerr << x<<", ";
 	cerr<<'\n';
}
#define debv(x) cerr<< #x<<" = ", debv_(x); 

int counter=1;
vii xy(1);
const int INF=1000000000;

int v2(int x){
	int sol=0;
	int ac=1;
	while (ac<x){
		sol++;
		ac*=2;
	}
	return sol;
}

int create_xy(vi v, int prof,int padre){
	if (prof<-10) return 0;
	//debv(v);
	// debr(prof);
	if (v.size()==1){
		if(prof==0) return v[0];
		else{
			xy.push_back(pii{padre,v[0]});
			counter++;
			return -counter+1;
		}
	}
	if (v.size()==2 and prof==1){
		xy.push_back(pii{v[0],v[1]});
		counter++;
		return -counter+1;
	}
	xy.push_back(pii{});
	int ind=counter;
	counter++;
	vi der;
	vi izq;

	int hastadonde=1;
	for (int i=0;i<prof-1;i++) hastadonde*=2;
	for (int i=0;i<v.size()-hastadonde;i++){
		if (i%2==0) izq.push_back(v[i]);
		else der.push_back(v[i]);
	}
	for (int i=v.size()-hastadonde;i<v.size();i++){
		if ((i+v.size()+hastadonde)%2==0) izq.push_back(v[i]);
		else der.push_back(v[i]);
	}

	xy[ind]=pii{create_xy(izq,prof-1,padre),create_xy(der,prof-1,padre)};
	return -ind;
}

void create_circuit(int n, vi ciclo) {
    int m=ciclo.size();
    ciclo.push_back(0);
    vvi conexiones(n+1);
    for (int i=0;i<m;i++) conexiones[ciclo[i]].push_back(ciclo[i+1]);
	for (int i=1;i<n+1;i++){
		if (conexiones[i].size()==0) conexiones[i].push_back(i);
	}
	vi salidas(n+1);
	salidas[0]=ciclo[0];
	for (int i=1;i<n+1;i++) salidas[i]=create_xy(conexiones[i],v2(conexiones[i].size()),-counter);
	vi switchX,switchY;

	for (int i=1;i<xy.size();i++){
		switchX.push_back(xy[i].first);
		switchY.push_back(xy[i].second);
	}
	//debv(salidas);
	//debv(switchX);
	//debv(switchY);
    answer(salidas, switchX, switchY);
}

Compilation message (stderr)

doll.cpp:15:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 | void debv_(auto v){
      |            ^~~~
doll.cpp: In function 'int create_xy(vi, int, int)':
doll.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i=0;i<v.size()-hastadonde;i++){
      |               ~^~~~~~~~~~~~~~~~~~~~
doll.cpp:64:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i=v.size()-hastadonde;i<v.size();i++){
      |                                 ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i=1;i<xy.size();i++){
      |               ~^~~~~~~~~~

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