oj.uz

Submission #206484

# Submission time Handle Problem Language Result Execution time Memory
206484 2020-03-03T12:47:58 Z spdskatr Mechanical Doll (IOI18_doll) C++14
100 / 100
 108 ms 15616 KB 
#include "doll.h"
#include <cassert>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <algorithm>
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

int target[1<<18], bitcnt, N, startpos, cnt;
vector<int> a, X, Y;
vector<pii> perm;
vector<int> seq[19];

// Returns ID to new node created
int create(int l, int r) {
	if (r < startpos) {
		return -1;
	}
	if (l == r) {
		return target[l];
	}
	int id = cnt++;
	X.push_back(0);
	Y.push_back(0);
	int mid = (l + r) / 2;
	int xv = create(l, mid);
	int yv = create(mid+1, r);
	X[id] = xv, Y[id] = yv;
	return -(id+1);
}

void create_circuit(int M, std::vector<int> A) {
	N = A.size() + 1; // N = N+1 :thonk:
	a = vector<int>(A);
	a.push_back(0);
	std::vector<int> C(M + 1);
	C[0] = -1;
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}
	if (A.size() == 1) {
		C[0] = A[0];
		C[A[0]] = 0;
		answer(C, X, Y);
		return;
	}
	bitcnt = 32 - __builtin_clz(N);
	seq[0].push_back(0);
	for (int i = 1; i <= bitcnt; i++) {
		for (int x : seq[i-1]) {
			seq[i].push_back(x);
			seq[i].push_back(x + (1 << (i-1)));
		}
	}
	startpos = (1 << bitcnt) - N;
	for (int i = startpos; i < seq[bitcnt].size(); i++) {
		perm.push_back({ seq[bitcnt][i], i });
	}
	assert(perm.size() == N);
	sort(perm.begin(), perm.end());
	for (int i = 0; i < N; i++) {
		target[perm[i].se] = a[i];
	}
	create(0, (1 << bitcnt) - 1);
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = startpos; i < seq[bitcnt].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:2:
doll.cpp:64:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |  assert(perm.size() == N);
      |         ~~~~~~~~~~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 43 ms 6456 KB Output is correct
3 Correct 37 ms 6296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 59 ms 8792 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 43 ms 6456 KB Output is correct
3 Correct 37 ms 6296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 59 ms 8792 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 67 ms 11064 KB Output is correct
9 Correct 75 ms 11928 KB Output is correct
10 Correct 108 ms 15616 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 43 ms 6456 KB Output is correct
3 Correct 37 ms 6296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 59 ms 8792 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 67 ms 11064 KB Output is correct
9 Correct 75 ms 11928 KB Output is correct
10 Correct 108 ms 15616 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 108 ms 15376 KB Output is correct
15 Correct 71 ms 10672 KB Output is correct
16 Correct 103 ms 14892 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 3 ms 204 KB Output is correct
20 Correct 103 ms 15392 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 1 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 60 ms 9952 KB Output is correct
3 Correct 59 ms 9924 KB Output is correct
4 Correct 98 ms 13816 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 60 ms 9952 KB Output is correct
3 Correct 59 ms 9924 KB Output is correct
4 Correct 98 ms 13816 KB Output is correct
5 Correct 101 ms 14852 KB Output is correct
6 Correct 101 ms 14752 KB Output is correct
7 Correct 102 ms 14732 KB Output is correct
8 Correct 100 ms 14496 KB Output is correct
9 Correct 62 ms 9884 KB Output is correct
10 Correct 99 ms 14464 KB Output is correct
11 Correct 108 ms 14188 KB Output is correct
12 Correct 84 ms 10324 KB Output is correct
13 Correct 76 ms 10396 KB Output is correct
14 Correct 71 ms 10452 KB Output is correct
15 Correct 64 ms 10608 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 64 ms 10136 KB Output is correct
18 Correct 61 ms 10168 KB Output is correct
19 Correct 76 ms 10172 KB Output is correct
20 Correct 95 ms 14348 KB Output is correct
21 Correct 95 ms 14092 KB Output is correct
22 Correct 106 ms 14184 KB Output is correct