Submission #418518

#	Time	Username	Problem	Language	Result	Execution time	Memory
418518		EncryptingWolf	Mechanical Doll (IOI18_doll)	C++14	6 / 100	97 ms	14000 KiB

doll

#include <vector>
#include "doll.h"
#include <iostream>
#include <queue>
#include <algorithm>
typedef long long ll;
#define FOR(i,x,y) for (ll i = x; i<y; i++)
using namespace std;



void create_circuit(int M, vector<int> A)
{
	A.push_back(0);
	M += 1;
	vector<int> connections(M,0);
	connections[0] = A[0];
	vector<pair<int,int>> switches;
	vector<vector<int>> follow(M);
	FOR(i, 0, A.size() - 1)
	{
		follow[A[i]].push_back(A[i + 1]);
	}
	int lowestSwitch = -1;
	FOR(i,1,M)
	{
		if (follow[i].size() == 1)
		{
			connections[i]=follow[i][0];
		}
		else if (follow[i].size() ==0)
		
		{
			continue;
		}
		else
		{
			connections[i] = lowestSwitch;
			switches.push_back({});
			lowestSwitch--;
			int switchStart = lowestSwitch;
			int num = 1;
			while (num*2 < follow[i].size())
			{
				int firstSwitch = switches.size() - num;
				FOR(j, firstSwitch, firstSwitch+num)
				{
					switches[j].first = lowestSwitch;
					switches[j].second = lowestSwitch-1;
					lowestSwitch -= 2;
					switches.push_back({});
					switches.push_back({});
				}
				num *= 2;
			}

			int firstSwitch = switches.size() - num;
			int outnum = num * 2;
			int z = 0;
			FOR(j, (firstSwitch*2), (firstSwitch + num)*2)
			{
				if (outnum > follow[i].size())
				{
					if (j % 2 == 0)
					{
						switches[j / 2].first = switchStart;
					}
					if (j % 2 == 1)
					{
						switches[j / 2].second = switchStart;
					}
				}
				else
				{
					if (j % 2 == 0)
					{
						switches[j / 2].first = follow[i][z];
					}
					if (j % 2 == 1)
					{
						switches[j / 2].second = follow[i][z];
					}
					z++;
				}
			}
		}
	}
	vector<int> X, Y;
	FOR(i, 0, switches.size())
	{
		X.push_back(switches[i].first);
		Y.push_back(switches[i].second);
	}


	answer(connections, X, Y);

}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:7:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for (ll i = x; i<y; i++)
......
   20 |  FOR(i, 0, A.size() - 1)
      |      ~~~~~~~~~~~~~~~~~~             
doll.cpp:20:2: note: in expansion of macro 'FOR'
   20 |  FOR(i, 0, A.size() - 1)
      |  ^~~
doll.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    while (num*2 < follow[i].size())
      |           ~~~~~~^~~~~~~~~~~~~~~~~~
doll.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (outnum > follow[i].size())
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
doll.cpp:7:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for (ll i = x; i<y; i++)
......
   89 |  FOR(i, 0, switches.size())
      |      ~~~~~~~~~~~~~~~~~~~~~          
doll.cpp:89:2: note: in expansion of macro 'FOR'
   89 |  FOR(i, 0, switches.size())
      |  ^~~

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