Submission #432564

#	Time	Username	Problem	Language	Result	Execution time	Memory
432564		frodakcin	Mechanical Doll (IOI18_doll)	C++11	53 / 100	152 ms	14548 KiB

doll

#include "doll.h"
#include <cstdio>
#include <cassert>
#include <vector>

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M + 1);
	std::vector<std::vector<int> > ord(M + 1, std::vector<int>());
  C[0] = A[0];
	for(int i=0;i<N;++i)
	{
		int nx = i+1==N?0:A[i+1];
		ord[A[i]].push_back(nx);
	}
	int S=0;
  std::vector<int> X, Y;
	for(int i=1;i<=M;++i)
	{
		if(ord[i].size() <= 1)
		{
			if(ord[i].empty())
				C[i]=0; // UNDEF
			else
				C[i]=ord[i][0];
		}
		else
		{
			int L = 31 - __builtin_clz((int)ord[i].size()-1) + 1;
			assert((1<<L >= ord[i].size()) && (ord[i].size() > 1<<L-1));

			C[i]=-(S+1);
			for(int j=1;j<(1<<L);++j)
				X.push_back(-(S+2*j)), Y.push_back(-(S+2*j+1));
			std::vector<int> path;
			for(int j=0;j<(1<<L-1);++j)
			{
				int k=1<<L-1;
				for(int b=0;b<L-1;++b)
					k |= (j>>b&1)<<L-2-b; // reverse bits of i
				path.push_back(S+k);
			}
			assert(path.size() == (1<<L-1));

			for(int x:path) X[x-1]=Y[x-1]=-(S+1);
			for(int j=0;j<path.size();++j)
				Y[path[path.size()-j-1]-1]=ord[i][ord[i].size()-1-j];
			for(int j=0;j+path.size()<ord[i].size();++j)
				X[path[path.size()-j-1]-1]=ord[i][ord[i].size()-path.size()-1-j];

			S += (1<<L)-1;
		}
	}
	//for(int x:Y) printf("%d\n", x);
  answer(C, X, Y);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:3:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    assert((1<<L >= ord[i].size()) && (ord[i].size() > 1<<L-1));
      |            ~~~~~^~~~~~~~~~~~~~~~
doll.cpp:30:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |    assert((1<<L >= ord[i].size()) && (ord[i].size() > 1<<L-1));
      |                                                          ~^~
doll.cpp:30:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |    assert((1<<L >= ord[i].size()) && (ord[i].size() > 1<<L-1));
      |                                       ~~~~~~~~~~~~~~^~~~~~~~
doll.cpp:36:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |    for(int j=0;j<(1<<L-1);++j)
      |                      ~^~
doll.cpp:38:15: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |     int k=1<<L-1;
      |              ~^~
doll.cpp:40:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |      k |= (j>>b&1)<<L-2-b; // reverse bits of i
      |                     ~~~^~
In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:3:
doll.cpp:43:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |    assert(path.size() == (1<<L-1));
      |                              ~^~
doll.cpp:43:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |    assert(path.size() == (1<<L-1));
      |           ~~~~~~~~~~~~^~~~~~~~~~~
doll.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for(int j=0;j<path.size();++j)
      |                ~^~~~~~~~~~~~

• 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