Submission #832443

#	Time	Username	Problem	Language	Result	Execution time	Memory
832443		caganyanmaz	Mechanical Doll (IOI18_doll)	C++17	60.67 / 100	58 ms	8536 KiB

doll

#include <bits/stdc++.h>
#define pb push_back
#include "doll.h"
using namespace std;

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

vector<int> a;
vector<int> x, y;
int n, m;


void create_circuit(int M, vector<int> A) 
{
	a = A;
	if (a.size() == (a.size()&(-a.size())))
		a.pb(0);
	n = a.size();
	int step_count = (a.size()+1)/2;
	int i;
	for (i = 0; i+step_count < a.size(); i++)
	{
		x.pb(a[i]);
		y.pb(a[i+step_count]);
	}
	if (n&1)
	{
		x.pb(a[i]);
		y.pb(0);
	}
	int l = 0, r = x.size();
	int depth = 0;
	while ((r-l) > 1)
	{
		depth++;
		step_count = (r+1 - l)/2;
		for (i = l; i+step_count < r; i++)
		{
			x.pb(-i-1);
			y.pb(-i-step_count-1);
		}
		if (1&(r-l))
		{
			x.pb(-i-1);
			y.pb(0);
		}
		l = r;
		r = x.size();
	}
	int root = -x.size();
	for (int i = 0; i < x.size(); i++)
	{
		if (x[i] == 0)
			x[i] = root;
		if (y[i] == 0)
			y[i] = root;
	}
	int last = root;
	i = x.size()-1;
	int d = 0;
	while (y[i] != root)
	{
		d++;
		i = -y[i]-1;
	}
	y[i] = -x.size()-1;
	int last_encounter = i;
	while (d < depth)
	{
		int xsize = x.size();
		d++;
		x.pb(last);
		y.pb(-xsize-2);
		last_encounter = y.size()-1;
	}
	y[last_encounter] = 0;
	vector<int> c(M+1, root);
	debug(c, x, y);
	answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (i = 0; i+step_count < a.size(); i++)
      |              ~~~~~~~~~~~~~^~~~~~~~~~
doll.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~

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