oj.uz

Submission #361700

# Submission time Handle Problem Language Result Execution time Memory
361700 2021-01-31T09:41:52 Z NachoLibre Mechanical Doll (IOI18_doll) C++17
100 / 100
 135 ms 12928 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
#ifndef wambule
#include "doll.h"
#else
void answer(vint c, vint x, vint y) {
}
#endif

int n, o, w;
vint a, x, y, c, cp;

int N() {
	++w;
	x.push_back(0);
	y.push_back(0);
	return w;
}

void C(int l, int r, int d, int x) {
	if(l == r) {
		c[l] = x;
		return;
	}
	int m = (l + r) / 2;
	C(l, m, d + 1, x);
	C(m + 1, r, d + 1, x + (1 << d));
}

void B(int l, int r, int z) {
	int m = (l + r) / 2;
	if(m < o - n + 1) {
		x[z - 1] = -1;
	} else if(l == m) {
		x[z - 1] = a[cp[l]];
	} else {
		x[z - 1] = -N();
		B(l, m, w);
	}
	if(r == m + 1) {
		y[z - 1] = a[cp[r]];
	} else {
		y[z - 1] = -N();
		B(m + 1, r, w);
	}
}

void create_circuit(int m, vint _a) {
	//  //  //  //  //  //  //  //
	a = _a;
	a.push_back(0);
	n = a.size();
	o = (1 << ((int)log2(n - 1) + 1));
	//  //  //  //  //  //  //  //
	c.resize(o + 1);
	C(1, o, 0, 0);
	vector<pair<int, int>> v;
	for(int i = o - n + 1; i <= o; ++i) {
		v.push_back({c[i], i});
	}
	sort(v.begin(), v.end()); cp = c;
	for(int i = 0; i < v.size(); ++i) {
		cp[v[i].second] = i;
	}
	//  //  //  //  //  //  //  //
	B(1, o, N());
	//  //  //  //  //  //  //  //
	answer(vector<int>(m + 1, -1), x, y);
	//  //  //  //  //  //  //  //
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Compilation message

doll.cpp: In function 'void create_circuit(int, vint)':
doll.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 0; i < v.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 43 ms 5876 KB Output is correct
3 Correct 40 ms 5480 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 972 KB Output is correct
6 Correct 63 ms 7656 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 5876 KB Output is correct
3 Correct 40 ms 5480 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 972 KB Output is correct
6 Correct 63 ms 7656 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 92 ms 9264 KB Output is correct
9 Correct 80 ms 9916 KB Output is correct
10 Correct 110 ms 12928 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 5876 KB Output is correct
3 Correct 40 ms 5480 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 972 KB Output is correct
6 Correct 63 ms 7656 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 92 ms 9264 KB Output is correct
9 Correct 80 ms 9916 KB Output is correct
10 Correct 110 ms 12928 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 120 ms 12332 KB Output is correct
15 Correct 96 ms 8900 KB Output is correct
16 Correct 122 ms 12488 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 121 ms 12876 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 2 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 70 ms 8516 KB Output is correct
3 Correct 63 ms 8480 KB Output is correct
4 Correct 100 ms 11776 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 70 ms 8516 KB Output is correct
3 Correct 63 ms 8480 KB Output is correct
4 Correct 100 ms 11776 KB Output is correct
5 Correct 119 ms 12164 KB Output is correct
6 Correct 110 ms 12120 KB Output is correct
7 Correct 135 ms 12272 KB Output is correct
8 Correct 116 ms 12036 KB Output is correct
9 Correct 68 ms 8600 KB Output is correct
10 Correct 98 ms 11972 KB Output is correct
11 Correct 105 ms 11752 KB Output is correct
12 Correct 63 ms 8636 KB Output is correct
13 Correct 66 ms 8620 KB Output is correct
14 Correct 66 ms 8756 KB Output is correct
15 Correct 66 ms 8728 KB Output is correct
16 Correct 4 ms 548 KB Output is correct
17 Correct 76 ms 7512 KB Output is correct
18 Correct 70 ms 8716 KB Output is correct
19 Correct 77 ms 8640 KB Output is correct
20 Correct 115 ms 12100 KB Output is correct
21 Correct 99 ms 12028 KB Output is correct
22 Correct 125 ms 12020 KB Output is correct