oj.uz

Submission #244484

# Submission time Handle Problem Language Result Execution time Memory
244484 2020-07-04T07:11:55 Z maximath_1 Mechanical Doll (IOI18_doll) C++11
100 / 100
 206 ms 14492 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> c, x, y, desti, state, l, r;
int id = 0, sz = 0;

int build(int nd, int tri){
	if(tri == 0) return -1;
	if(nd == 1) return id++;

	int nw = - sz - 1; sz ++;
	l[-nw] = build(nd/2, tri - min(nd/2, tri));
	r[-nw] = build(nd/2, min(nd/2, tri));

	return nw;
}

int dfs(int nw){
	if(nw >= 0) return nw;
	state[-nw] = 1 - state[-nw];
	if(state[-nw]) return dfs(l[-nw]);
	else return dfs(r[-nw]);
}

void create_circuit(int m, vector<int> a){
	a.push_back(0);

	int k = 1;
	for(; k < a.size(); k *= 2);
	
	l.resize(k); r.resize(k); state.resize(k);
	build(k, a.size());

	c.assign(m + 1, -1);
	desti.resize(2 * id);
	x.resize(sz); y.resize(sz);

	for(int i = 0; i < a.size(); i++)
		desti[dfs(-1)] = a[i];

	for(int i = 1; i <= sz; i++){
		x[i - 1] = l[i];
		y[i - 1] = r[i];
		if(x[i - 1] >= 0) x[i - 1] = desti[x[i - 1]];
		if(y[i - 1] >= 0) y[i - 1] = desti[y[i - 1]];
	}

	answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(; k < a.size(); k *= 2);
      |        ~~^~~~~~~~~~
doll.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < a.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 58 ms 5988 KB Output is correct
3 Correct 52 ms 5912 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1372 KB Output is correct
6 Correct 79 ms 8036 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 58 ms 5988 KB Output is correct
3 Correct 52 ms 5912 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1372 KB Output is correct
6 Correct 79 ms 8036 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 10556 KB Output is correct
9 Correct 101 ms 11176 KB Output is correct
10 Correct 155 ms 14492 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 58 ms 5988 KB Output is correct
3 Correct 52 ms 5912 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1372 KB Output is correct
6 Correct 79 ms 8036 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 10556 KB Output is correct
9 Correct 101 ms 11176 KB Output is correct
10 Correct 155 ms 14492 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 152 ms 13976 KB Output is correct
15 Correct 91 ms 10040 KB Output is correct
16 Correct 154 ms 13880 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 162 ms 14240 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 104 ms 9148 KB Output is correct
3 Correct 94 ms 9148 KB Output is correct
4 Correct 143 ms 12304 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 104 ms 9148 KB Output is correct
3 Correct 94 ms 9148 KB Output is correct
4 Correct 143 ms 12304 KB Output is correct
5 Correct 164 ms 13592 KB Output is correct
6 Correct 180 ms 13336 KB Output is correct
7 Correct 160 ms 13348 KB Output is correct
8 Correct 206 ms 13092 KB Output is correct
9 Correct 119 ms 9148 KB Output is correct
10 Correct 139 ms 12904 KB Output is correct
11 Correct 141 ms 12580 KB Output is correct
12 Correct 90 ms 9416 KB Output is correct
13 Correct 97 ms 9844 KB Output is correct
14 Correct 101 ms 9856 KB Output is correct
15 Correct 99 ms 10048 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 97 ms 7852 KB Output is correct
18 Correct 101 ms 9404 KB Output is correct
19 Correct 96 ms 9400 KB Output is correct
20 Correct 146 ms 12896 KB Output is correct
21 Correct 142 ms 12540 KB Output is correct
22 Correct 202 ms 12676 KB Output is correct