oj.uz

Submission #248551

# Submission time Handle Problem Language Result Execution time Memory
248551 2020-07-12T17:25:39 Z kostia244 Mechanical Doll (IOI18_doll) C++17
100 / 100
 256 ms 11568 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1<<29;
int n, m;
vector<int> x, y;
int build(vector<int> a, int S) {
	//cout << S << " " << a.size() << endl;
	if(a.empty() || a.back() == -1) return -1;
	if(S == 1) return -inf;
	x.push_back(0);
	y.push_back(0);
	int id = (int)x.size();
	int cur = 1, t = max(0, (int)a.size() - (S/2));
	vector<int> b[2];
	//for(auto i : a) cout << i << " "; cout << "\n to \n";
	while(a.size()) {
		if(b[0].size() == t && !cur) cur = 1;
		b[cur].push_back(a.back());
		a.pop_back();
		cur ^= 1;
	}
	for(int j = 0; j < 2; j++){
		reverse(b[j].begin(), b[j].end());
		//for(auto i : b[j]) cout << i << " "; cout << '\n';
	}
	int tt = build(b[0], S/2);
	x[id-1] = tt;
	tt = build(b[1], S/2);
	y[id-1] = tt;
	return -id;
}
void create_circuit(int M, vector<int> A) {
	m = M, n = A.size();
	A.push_back(0);
	int t = A.size();
	while(t&(t-1)) t++;
	build(A, t);
	//for(int i = 0; i < x.size(); i++) cout << i+1 << " " << x[i] << " " << y[i] << '\n';
	int id = 0;
	vector<int> st(x.size());
	for(int p = 0, j = 0, i = 0; j < A.size(); i++) {
		if(p < 0 && (st[-p - 1] ? y : x)[-p - 1] == -inf) {
			(st[-p - 1] ? y : x)[-p - 1] = A[j++];
		}
		if(p < 0) {
			p = -p - 1;
			int op = p;
			if(!st[p]) st[p] = 1, p = x[p];
			else st[p] = 0, p = y[p];
		} else p = -1;
	}
	//cout << '\n';
	answer(vector<int>(m+1, -1), x, y);
}

Compilation message

doll.cpp: In function 'int build(std::vector<int>, int)':
doll.cpp:18:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |   if(b[0].size() == t && !cur) cur = 1;
      |      ~~~~~~~~~~~~^~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:42:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int p = 0, j = 0, i = 0; j < A.size(); i++) {
      |                               ~~^~~~~~~~~~
doll.cpp:48:8: warning: unused variable 'op' [-Wunused-variable]
   48 |    int op = p;
      |        ^~
doll.cpp:40:6: warning: unused variable 'id' [-Wunused-variable]
   40 |  int id = 0;
      |      ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 72 ms 4532 KB Output is correct
3 Correct 63 ms 4140 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 996 KB Output is correct
6 Correct 96 ms 6220 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 72 ms 4532 KB Output is correct
3 Correct 63 ms 4140 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 996 KB Output is correct
6 Correct 96 ms 6220 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 144 ms 8256 KB Output is correct
9 Correct 132 ms 7912 KB Output is correct
10 Correct 207 ms 11568 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 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 72 ms 4532 KB Output is correct
3 Correct 63 ms 4140 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 996 KB Output is correct
6 Correct 96 ms 6220 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 144 ms 8256 KB Output is correct
9 Correct 132 ms 7912 KB Output is correct
10 Correct 207 ms 11568 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 241 ms 10848 KB Output is correct
15 Correct 180 ms 8224 KB Output is correct
16 Correct 214 ms 11376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 256 ms 10876 KB Output is correct
21 Correct 2 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 2 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 120 ms 7564 KB Output is correct
3 Correct 160 ms 7184 KB Output is correct
4 Correct 216 ms 10496 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 120 ms 7564 KB Output is correct
3 Correct 160 ms 7184 KB Output is correct
4 Correct 216 ms 10496 KB Output is correct
5 Correct 199 ms 11260 KB Output is correct
6 Correct 204 ms 10604 KB Output is correct
7 Correct 235 ms 11284 KB Output is correct
8 Correct 192 ms 10192 KB Output is correct
9 Correct 135 ms 7204 KB Output is correct
10 Correct 210 ms 10884 KB Output is correct
11 Correct 187 ms 10268 KB Output is correct
12 Correct 132 ms 7304 KB Output is correct
13 Correct 164 ms 8004 KB Output is correct
14 Correct 120 ms 7560 KB Output is correct
15 Correct 199 ms 7620 KB Output is correct
16 Correct 5 ms 460 KB Output is correct
17 Correct 111 ms 6332 KB Output is correct
18 Correct 116 ms 7712 KB Output is correct
19 Correct 115 ms 7304 KB Output is correct
20 Correct 225 ms 10384 KB Output is correct
21 Correct 193 ms 10836 KB Output is correct
22 Correct 214 ms 10892 KB Output is correct