Submission #1032983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032983		parsadox2	Mechanical Doll (IOI18_doll)	C++17	68.91 / 100	89 ms	18456 KiB

doll

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

using namespace std;

const int N = 2e5 + 10;
int n , m;
vector <int> C , X , Y , adj[N];

int Rev(int x , int cnt)
{
	int res = 0;
	for(int i = 0 ; i < cnt ; i++)  if((x >> i) & 1)
		res |= (1 << (cnt - i - 1));
	return res;
}

int Solve(vector <int> vec , bool flg = true)
{
	if(vec.size() == 1)
		return vec[0];
	X.push_back(0);
	Y.push_back(0);
	int now = X.size();
	vector <int> v[2];
	if(flg)
	{
		int tmp = 1 , cnt = 0;
		while(tmp < vec.size())
		{
			tmp *= 2;
			cnt++;
		}
		vector <int> fake(tmp , 0);
		for(int i = 0 ; i < tmp - vec.size() ; i++)
			fake[Rev(i , cnt)] = -now;
		int pos = 0;
		for(int i = 0 ; i < tmp ; i++)  if(fake[i] != -now)
		{
			fake[i] = vec[pos];
			pos++;
		}
		vec = fake;
	}
	bool eq = true;
	for(int i = 1 ; i < vec.size() ; i++)  if(vec[i] != vec[0])
		eq = false;
	if(eq)
	{
		X[now - 1] = vec[0];
		Y[now - 1] = vec[0];
		return -now;
	}
	for(int i = 0 ; i < vec.size() ; i++)
		v[i % 2].push_back(vec[i]);
	int tmp = Solve(v[0] , 0);
	X[now - 1] = tmp;
	tmp = Solve(v[1] , 0);
	Y[now - 1] = tmp;
	return -1 * now;
}

void Build(int v)
{
	if(adj[v].empty())
	{
		C[v] = 0;
		return;
	}
	int tmp = Solve(adj[v]);
	C[v] = tmp;
}

void create_circuit(int mm , vector <int> A)
{
	n = A.size();
	m = mm;
	C.resize(m + 1);
	adj[0].push_back(A[0]);
	for(int i = 0 ; i + 1 < n ; i++)
		adj[A[i]].push_back(A[i + 1]);
	adj[A.back()].push_back(0);
	for(int i = 0 ; i <= m ; i++)
	{
		Build(i);
	}
	answer(C , X , Y);
}

Compilation message (stderr)

doll.cpp: In function 'int Solve(std::vector<int>, bool)':
doll.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   while(tmp < vec.size())
      |         ~~~~^~~~~~~~~~~~
doll.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0 ; i < tmp - vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~~~~~~~
doll.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 1 ; i < vec.size() ; i++)  if(vec[i] != vec[0])
      |                  ~~^~~~~~~~~~~~
doll.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0 ; i < vec.size() ; i++)
      |                  ~~^~~~~~~~~~~~

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