oj.uz

Submission #312685

# Submission time Handle Problem Language Result Execution time Memory
312685 2020-10-14T04:45:38 Z tengiz05 Mechanical Doll (IOI18_doll) C++17
100 / 100
 89 ms 10404 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
int sz=1, n, cnt=0;
void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	n = a.size();
	while(sz < n)sz<<=1, cnt++;
	vector<int> t(sz*2);
	for(int i=0;i<sz;i++)t[i+sz] = inf;
	int tt = 0;
	vector<int> rev(sz);
	for(int i=0;i<sz;i++)rev[i] = rev[i/2]/2|((i&1)<<(cnt-1));
	int j=0;
	for(int i=0;i<sz;i++){
		if(rev[i] >= sz-n)t[rev[i]+sz] = a[j], j++;
		else t[rev[i]+sz] = inf;
	}
	vector<int> X, Y;
	for(int i=sz-1; i>0; i--){
		if(t[i*2] == inf && t[i*2+1] == inf)t[i] = inf;
		else {
			t[i] = --tt;
			X.push_back(t[i*2]);
			Y.push_back(t[i*2+1]);
		}
	}for(int i=0;i<(int)X.size();i++){
		if(X[i] == inf)X[i] = tt;
		if(Y[i] == inf)Y[i] = tt;
	}
	answer(vector<int>(m+1, tt), X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 42 ms 4892 KB Output is correct
3 Correct 32 ms 4648 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 984 KB Output is correct
6 Correct 51 ms 5804 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 42 ms 4892 KB Output is correct
3 Correct 32 ms 4648 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 984 KB Output is correct
6 Correct 51 ms 5804 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 7892 KB Output is correct
9 Correct 62 ms 8172 KB Output is correct
10 Correct 82 ms 10404 KB Output is correct
11 Correct 2 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 42 ms 4892 KB Output is correct
3 Correct 32 ms 4648 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 984 KB Output is correct
6 Correct 51 ms 5804 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 7892 KB Output is correct
9 Correct 62 ms 8172 KB Output is correct
10 Correct 82 ms 10404 KB Output is correct
11 Correct 2 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 80 ms 10144 KB Output is correct
15 Correct 53 ms 7668 KB Output is correct
16 Correct 78 ms 10024 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 84 ms 10148 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 256 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 54 ms 7376 KB Output is correct
3 Correct 55 ms 7404 KB Output is correct
4 Correct 73 ms 9640 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 54 ms 7376 KB Output is correct
3 Correct 55 ms 7404 KB Output is correct
4 Correct 73 ms 9640 KB Output is correct
5 Correct 76 ms 9888 KB Output is correct
6 Correct 77 ms 9780 KB Output is correct
7 Correct 78 ms 9776 KB Output is correct
8 Correct 76 ms 9636 KB Output is correct
9 Correct 52 ms 7376 KB Output is correct
10 Correct 89 ms 9600 KB Output is correct
11 Correct 80 ms 9524 KB Output is correct
12 Correct 49 ms 7508 KB Output is correct
13 Correct 53 ms 7504 KB Output is correct
14 Correct 55 ms 7632 KB Output is correct
15 Correct 65 ms 7632 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 46 ms 6216 KB Output is correct
18 Correct 50 ms 7412 KB Output is correct
19 Correct 50 ms 7400 KB Output is correct
20 Correct 79 ms 9624 KB Output is correct
21 Correct 75 ms 9640 KB Output is correct
22 Correct 81 ms 9640 KB Output is correct