Submission #832350

#	Time	Username	Problem	Language	Result	Execution time	Memory
832350		caganyanmaz	Mechanical Doll (IOI18_doll)	C++17	60.67 / 100	50 ms	9828 KiB

doll

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


#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)>>1;
	int i;
	for (i = 0; i+step_count < a.size(); i++)
	{
		x.pb(a[i]);
		y.pb(a[i+step_count]);
	}
	if (i < step_count)
	{
		x.pb(a[i]);
		y.pb(0);
	}
	int l = 0, r = x.size();
	debug(x, y);
	int depth = 0;
	while ((r-l) > 1)
	{
		depth++;
		step_count = (r+1 - l)/2;
		debug(step_count);
		debug(l, r);
		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();
	}
	debug(x, y, depth);
	int oooo = -x.size();
	for (int i = 0; i < x.size(); i++)
	{
		if (x[i] == 0)
			x[i] = -x.size();
		if (y[i] == 0)
			y[i] = -y.size();
	}
	int last = -x.size();
	i = x.size()-1;
	int d = 0;
	while (y[i] != -x.size())
	{
		d++;
		i = -y[i]-1;
	}
	debug(i);
	y[i] = -x.size()-1;
	
	int lss = i;
	while (d < depth)
	{
		int ss = x.size();
		d++;
		x.pb(last);
		y.pb(-ss-2);
		lss = y.size()-1;
	
	}

	y[lss] = 0;
	vector<int> c(M+1, oooo);
	debug(x, y);
	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:60:20: 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 < x.size(); i++)
      |                  ~~^~~~~~~~~~
doll.cpp:70:14: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  while (y[i] != -x.size())

• 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