oj.uz

Submission #297683

# Submission time Handle Problem Language Result Execution time Memory
297683 2020-09-11T18:16:11 Z Berted Mechanical Doll (IOI18_doll) C++14
100 / 100
 127 ms 11936 KB 
#include "doll.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <queue>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

vector<int> C, X, Y;
vector<pii> candidate;
int sz1 = 0;

inline void fill(int u, int sz, int num)
{
	if (sz == 2)
	{
		candidate.push_back({num | (sz1 / sz), -(u + 1)});
		candidate.push_back({num, u + 1});
	}
	else
	{
		X.push_back(0); Y.push_back(0);
		X[u] = -X.size();
		fill(X.size() - 1, sz / 2, num);
		X.push_back(0); Y.push_back(0);
		Y[u] = -X.size();
		fill(X.size() - 1, sz / 2, num | (sz1 / sz));
	}
}

inline void rs(int u, int sz, int esz, int num)
{
	if (sz == 2)
	{
		candidate.push_back({num | (sz1 / sz), -u - 1});
		if (esz & 1) {candidate.push_back({num, u + 1});}
		else {X[u] = -1;}
	}
	else
	{
		X.push_back(0); Y.push_back(0);
		Y[u] = -Y.size();
		rs(Y.size() - 1, sz / 2, esz, num | (sz1 / sz));
		if (esz & (sz / 2)) 
		{
			X.push_back(0); Y.push_back(0);
			X[u] = -X.size();
			fill(X.size() - 1, sz / 2, num);
		} 
		else {X[u] = -1;}
	}
}

void buildSwitch(int size)
{
	if (size == 2) 
	{
		sz1 = 2;
		fill(0, 2, 0);
		return;
	}
	sz1 = 1;
	while (sz1 < size) {sz1 <<= 1;}

	X.push_back(0); Y.push_back(0);
	X[0] = -X.size();
	X.push_back(0); Y.push_back(0);
	Y[0] = -X.size();

	rs(-X[0] - 1, sz1 / 2, (sz1 / 2) - 1, 0);
	rs(-Y[0] - 1, sz1 / 2, size - (sz1 / 2) - 1, 1);

	//cerr << "SIZE : " << u << " " << adj[u].size() << "\n";
}

void create_circuit(int M, vector<int> A)
{
	C.assign(M + 1, 0);
	A.push_back(0); X.push_back(0); Y.push_back(0);
	for (int i = 0; i <= M; i++) {C[i] = -X.size();}

	buildSwitch(A.size());
	sort(candidate.begin(), candidate.end());
	assert(candidate.size() == A.size());

	for (int i = 0; i < candidate.size(); i++)
	{
		//cerr << "Candidate : " << candidate[i].fst << " " << candidate[i].snd << "\n";
		if (candidate[i].snd < 0)
		{
			Y[-candidate[i].snd - 1] = A[i];
		}
		else
		{
			X[candidate[i].snd - 1] = A[i];
		}
	}

	candidate.clear();

	answer(C, X, Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 4860 KB Output is correct
3 Correct 43 ms 4296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 58 ms 6732 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 1 ms 204 KB Output is correct
2 Correct 49 ms 4860 KB Output is correct
3 Correct 43 ms 4296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 58 ms 6732 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 66 ms 7588 KB Output is correct
9 Correct 71 ms 8096 KB Output is correct
10 Correct 119 ms 11936 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 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 1 ms 204 KB Output is correct
2 Correct 49 ms 4860 KB Output is correct
3 Correct 43 ms 4296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 58 ms 6732 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 66 ms 7588 KB Output is correct
9 Correct 71 ms 8096 KB Output is correct
10 Correct 119 ms 11936 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 119 ms 11444 KB Output is correct
15 Correct 91 ms 7096 KB Output is correct
16 Correct 111 ms 11020 KB Output is correct
17 Correct 1 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 103 ms 11696 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 6016 KB Output is correct
3 Correct 57 ms 6024 KB Output is correct
4 Correct 93 ms 9708 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 6016 KB Output is correct
3 Correct 57 ms 6024 KB Output is correct
4 Correct 93 ms 9708 KB Output is correct
5 Correct 103 ms 10844 KB Output is correct
6 Correct 127 ms 10524 KB Output is correct
7 Correct 96 ms 10524 KB Output is correct
8 Correct 95 ms 10400 KB Output is correct
9 Correct 66 ms 6076 KB Output is correct
10 Correct 95 ms 10268 KB Output is correct
11 Correct 90 ms 10012 KB Output is correct
12 Correct 57 ms 6312 KB Output is correct
13 Correct 61 ms 6748 KB Output is correct
14 Correct 62 ms 6812 KB Output is correct
15 Correct 65 ms 6964 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 66 ms 6788 KB Output is correct
18 Correct 57 ms 6232 KB Output is correct
19 Correct 56 ms 6324 KB Output is correct
20 Correct 95 ms 10236 KB Output is correct
21 Correct 96 ms 9940 KB Output is correct
22 Correct 91 ms 10044 KB Output is correct