Submission #119207

#	Time	Username	Problem	Language	Result	Execution time	Memory
119207		joseacaz	Mechanical Doll (IOI18_doll)	C++17	2 / 100	1080 ms	13140 KiB

doll

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

using namespace std;

int N, M, freq[MAXM], maxFreq, S, cnt = 0;
vector < int > A, C, X, Y, nxt[MAXM];

void max_self ( int& _a, int _b )
{
	_a = max ( _a, _b );
}

void create_circuit ( int _M, vector <int> _A )
{
	N = _A.size();
	M = _M;
	swap ( A, _A );

	for ( int i = 1; i < A.size(); i++ )
		nxt[A[i - 1]].push_back ( A[i] );
	nxt[0].push_back ( A[0] );
	nxt[A[A.size() - 1]].push_back ( 0 );

	freq[0] = 1;
	for ( auto i : A )
		freq[i]++;
	
	for ( int i = 1; i <= M; i++ )
		max_self ( maxFreq, freq[i] );
	
	if ( maxFreq <= 4 )
	{
		for ( int i = 1; i <= M; i++ )
		{
			if ( freq[i] == 2 )
				S++;
			else if ( freq[i] == 3 or freq[i] == 4 )
				S += 3;
		}

		C.resize ( M + 1 );
		X.resize ( S );
		Y.resize ( S );

		for ( int i = 0; i <= M; i++ )
		{
			if ( freq[i] == 0 )
				C[i] = 0;
			else if ( freq[i] == 1 )
				C[i] = nxt[i][0];
			else if ( freq[i] == 2 )
			{
				C[i] = --cnt;
				X[-C[i] - 1] = nxt[i][0];
				Y[-C[i] - 1] = nxt[i][1];
			}
			else if ( freq[i] == 3 )
			{
				C[i] = --cnt;
				X[-C[i] - 1] = --cnt;
				Y[-C[i] - 1] = --cnt;

				X[-X[-C[i] - 1] - 1] = C[i];
				X[-Y[-C[i] - 1] - 1] = nxt[i][0];
				Y[-X[-C[i] - 1] - 1] = nxt[i][1];
				Y[-Y[-C[i] - 1] - 1] = nxt[i][2];
			}
			else if ( freq[i] == 4 )
			{
				C[i] = --cnt;
				X[-C[i] - 1] = --cnt;
				Y[-C[i] - 1] = --cnt;

				X[-X[-C[i] - 1] - 1] = nxt[i][0];
				X[-Y[-C[i] - 1] - 1] = nxt[i][1];
				Y[-X[-C[i] - 1] - 1] = nxt[i][2];
				Y[-Y[-C[i] - 1] - 1] = nxt[i][3];
			}
		}

		for ( auto i : C )
			cerr << i << " ";
		cerr << "\n";
		
		for ( auto i : X )
			cerr << i << " ";
		cerr << "\n";

		for ( auto i : Y )
			cerr << i << " ";
		cerr << "\n";
	}

	answer ( C, X, Y );
}

Compilation message (stderr)

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

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