oj.uz

Submission #418566

# Submission time Handle Problem Language Result Execution time Memory
418566 2021-06-05T14:03:18 Z EncryptingWolf Mechanical Doll (IOI18_doll) C++14
53 / 100
 146 ms 20484 KB 
#include <vector>
#include "doll.h"
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
typedef long long ll;
#define FOR(i,x,y) for (ll i = x; i<y; i++)
using namespace std;


long long reverse(long long a, long long num)
{
	long long p = (long long)(log2(num) + 0.001);
	ll r=0;
	FOR(i, 0, p)
	{
		if ((a >> i) & 1)
		{
			r +=( 1 << (p - i-1));
		}
	}
	return r;
}

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;
			int switchStart = lowestSwitch;

			switches.push_back({});
			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(k, 0, outnum)
			{
				int j = reverse(k, outnum)+ (firstSwitch * 2);
				if (outnum-k > 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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 31 ms 6380 KB Output is correct
3 Correct 26 ms 5160 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 40 ms 7740 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 31 ms 6380 KB Output is correct
3 Correct 26 ms 5160 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 40 ms 7740 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 59 ms 7964 KB Output is correct
9 Correct 61 ms 9256 KB Output is correct
10 Correct 98 ms 12068 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 31 ms 6380 KB Output is correct
3 Correct 26 ms 5160 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 40 ms 7740 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 59 ms 7964 KB Output is correct
9 Correct 61 ms 9256 KB Output is correct
10 Correct 98 ms 12068 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 110 ms 12568 KB Output is correct
15 Correct 57 ms 7632 KB Output is correct
16 Correct 87 ms 11532 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 96 ms 13464 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 204 KB Output is partially correct
2 Correct 55 ms 7616 KB Output is correct
3 Partially correct 90 ms 11204 KB Output is partially correct
4 Partially correct 101 ms 12564 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 204 KB Output is partially correct
2 Correct 55 ms 7616 KB Output is correct
3 Partially correct 90 ms 11204 KB Output is partially correct
4 Partially correct 101 ms 12564 KB Output is partially correct
5 Partially correct 123 ms 17028 KB Output is partially correct
6 Partially correct 130 ms 18876 KB Output is partially correct
7 Partially correct 128 ms 18464 KB Output is partially correct
8 Partially correct 132 ms 20456 KB Output is partially correct
9 Partially correct 90 ms 12804 KB Output is partially correct
10 Partially correct 139 ms 20484 KB Output is partially correct
11 Partially correct 146 ms 20216 KB Output is partially correct
12 Partially correct 86 ms 13180 KB Output is partially correct
13 Partially correct 86 ms 12128 KB Output is partially correct
14 Partially correct 84 ms 11904 KB Output is partially correct
15 Partially correct 81 ms 10888 KB Output is partially correct
16 Partially correct 2 ms 588 KB Output is partially correct
17 Partially correct 69 ms 10436 KB Output is partially correct
18 Partially correct 71 ms 10408 KB Output is partially correct
19 Partially correct 75 ms 11024 KB Output is partially correct
20 Partially correct 101 ms 15028 KB Output is partially correct
21 Partially correct 116 ms 16512 KB Output is partially correct
22 Partially correct 98 ms 13172 KB Output is partially correct