oj.uz

Submission #102090

# Submission time Handle Problem Language Result Execution time Memory
102090 2019-03-22T07:31:35 Z bert30702 Mechanical Doll (IOI18_doll) C++17
73.4718 / 100
 169 ms 10544 KB 
#include <bits/stdc++.h>
 #include "doll.h"
using namespace std;
const int MX = 1e6 + 1000;
int ptr = 0;
int x[MX], y[MX], c[MX];
//void answer(vector<int> c, vector<int> x, vector<int> y) {
//	cout << 9 << ' ' << x.size() << endl;
//	for(auto it: c) cout << it << ' '; cout << endl;
//	for(auto it: x) cout << it << ' '; cout << endl;
//	for(auto it: y) cout << it << ' '; cout << endl;
//}
int build(vector<int> v) {
	if(v.size() == 1) return v[0];
	if(ptr != 0 and *max_element(v.begin(), v.end()) == *min_element(v.begin(), v.end()) and v[0] == -1) return v[0];
	int d = --ptr;
	vector<int> a, b;
	for(int i = 0; i < v.size(); i ++) {
		if(i & 1) b.push_back(v[i]);
		else      a.push_back(v[i]);
	}
	x[-d] = build(a);
	y[-d] = build(b);
	return d;
}
void create_circuit(int n, vector<int> v) {
	// for(auto it: v) cout << it << ' '; cout << endl;
	vector<int> a(v.begin() + 1, v.end()); a.push_back(0);
	// for(auto it: a) cout << it << ' '; cout << endl;
	int k = max(2, 1 << __lg(a.size() * 2 - 1));
	// cout << " ss " << k << ' ' << a.size() << endl;
	vector<int> tmp(k), GG(k, 0);
	int need = k - a.size();
	for(int i = k / 2; i >= 1; i >>= 1) {
		for(int j = 0; j < k; j += i) {
			if(!GG[j] and need) {
				GG[j] = true, tmp[j] = -1, need --;
			}
		}
	}
	for(int i = k - 1; i >= 0; i --) {
		if(!GG[i]) tmp[i] = a.back(), a.pop_back();
	}
	// for(auto it: tmp) cout << it << ' '; cout << endl;
	build(tmp); c[0] = v[0];
	for(int i = 1; i <= n; i ++) c[i] = -1;
	answer(
		vector<int>(c, c + n + 1),
		vector<int>(x + 1, x + 1 - ptr),
		vector<int>(y + 1, y + 1 - ptr)
	);
}
//main () {
//	// create_circuit(4, {1, 2, 1, 3});
//	create_circuit(1, vector<int> (33, 1));
//}

Compilation message

doll.cpp: In function 'int build(std::vector<int>)':
doll.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < v.size(); i ++) {
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 4768 KB Output is correct
3 Correct 53 ms 4652 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Incorrect 101 ms 6812 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 4768 KB Output is correct
3 Correct 53 ms 4652 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Incorrect 101 ms 6812 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 4768 KB Output is correct
3 Correct 53 ms 4652 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Incorrect 101 ms 6812 KB Output isn't correct
7 Halted 0 ms 0 KB -

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
15.4390812408 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 86 ms 6588 KB Output is correct
3 Correct 88 ms 8936 KB Output is correct
4 Partially correct 155 ms 10544 KB Output is partially correct

Subtask #6
48.0326971936 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 86 ms 6588 KB Output is correct
3 Correct 88 ms 8936 KB Output is correct
4 Partially correct 155 ms 10544 KB Output is partially correct
5 Partially correct 153 ms 10480 KB Output is partially correct
6 Partially correct 145 ms 10428 KB Output is partially correct
7 Partially correct 151 ms 10416 KB Output is partially correct
8 Partially correct 169 ms 10472 KB Output is partially correct
9 Partially correct 91 ms 9012 KB Output is partially correct
10 Partially correct 149 ms 10416 KB Output is partially correct
11 Partially correct 141 ms 10416 KB Output is partially correct
12 Correct 105 ms 8972 KB Output is correct
13 Correct 88 ms 7092 KB Output is correct
14 Correct 99 ms 9004 KB Output is correct
15 Correct 101 ms 9028 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 89 ms 6812 KB Output is correct
18 Correct 86 ms 6824 KB Output is correct
19 Correct 91 ms 9000 KB Output is correct
20 Partially correct 141 ms 10468 KB Output is partially correct
21 Partially correct 155 ms 10412 KB Output is partially correct
22 Partially correct 142 ms 10468 KB Output is partially correct