oj.uz

Submission #415783

# Submission time Handle Problem Language Result Execution time Memory
415783 2021-06-01T13:57:11 Z LastRonin Mechanical Doll (IOI18_doll) C++14
100 / 100
 198 ms 16620 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pill pair<ll, ll>
#define ex exit(0)
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;

const ll N = 8e5 + 100;

ll L[N], R[N];
int g[N], cur = 0, n;
vector<pill> x;
bool was[N];

void rec(ll v, ll l, ll r, ll z) {
	ll m = (l + r) >> 1ll;
	if(l == m) {
		if(z == 1)
			L[v] = 1000001;
		return;
	}	
	if(m - l + 1 > z) {
		L[v] = ++cur, rec(L[v], l, m, z);
		R[v] = ++cur, rec(R[v], m + 1, r, 0);
	}
	else {
		L[v] = 1000001, 
		R[v] = ++cur, rec(R[v], m + 1, r, z - (m - l + 1));
	}
}
void spusk(int v) {
	if(v == 1000001)return;
	if(was[v]) {
		was[v] = 0;
	    return (void)(R[v] == 0 ? x.pb(mp(v, 1)) : spusk(R[v]));
	}
	was[v] = 1;
	return (void)(L[v] == 0 ? x.pb(mp(v, 0)) : spusk(L[v]));	
}

void create_circuit(int m, vector<int> a) {
	n = a.size();
	a.pb(0);
	vector<int> C(m + 1, -1), X, Y;
	C[0] = a[0];    	
	ll z = __lg(n) + 1;
	ll d = (1<<z) - (n + 1);
	rec(0, 1, 1<<z, d);
	ll k = (1<<z);
	while(k--)spusk(0);
	for(int i = 1; i < (int)a.size(); i++)
		if(x[i].s)R[x[i].f] = a[i] + 1000002;
		else L[x[i].f] = a[i] + 1000002;
	for(int i = 0; i <= cur; i++) {
		if(L[i] > 1000000) 
			X.pb(L[i] - 1000002);
		else
			X.pb(-(L[i] + 1));
		if(R[i] > 1000000) 
			Y.pb(R[i] - 1000002);
		else
			Y.pb(-(R[i] + 1));
			
	}
	answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 54 ms 6416 KB Output is correct
3 Correct 45 ms 6392 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 79 ms 9404 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 2 ms 204 KB Output is correct
2 Correct 54 ms 6416 KB Output is correct
3 Correct 45 ms 6392 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 79 ms 9404 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 94 ms 10900 KB Output is correct
9 Correct 89 ms 11624 KB Output is correct
10 Correct 148 ms 16620 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 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 2 ms 204 KB Output is correct
2 Correct 54 ms 6416 KB Output is correct
3 Correct 45 ms 6392 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 79 ms 9404 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 94 ms 10900 KB Output is correct
9 Correct 89 ms 11624 KB Output is correct
10 Correct 148 ms 16620 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 177 ms 15880 KB Output is correct
15 Correct 100 ms 10396 KB Output is correct
16 Correct 130 ms 15848 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 180 ms 16320 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 76 ms 9640 KB Output is correct
3 Correct 96 ms 9692 KB Output is correct
4 Correct 159 ms 14636 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 76 ms 9640 KB Output is correct
3 Correct 96 ms 9692 KB Output is correct
4 Correct 159 ms 14636 KB Output is correct
5 Correct 161 ms 15704 KB Output is correct
6 Correct 198 ms 15528 KB Output is correct
7 Correct 132 ms 15584 KB Output is correct
8 Correct 160 ms 15388 KB Output is correct
9 Correct 85 ms 9656 KB Output is correct
10 Correct 150 ms 15288 KB Output is correct
11 Correct 124 ms 15108 KB Output is correct
12 Correct 82 ms 9892 KB Output is correct
13 Correct 88 ms 10196 KB Output is correct
14 Correct 104 ms 10220 KB Output is correct
15 Correct 96 ms 10260 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 80 ms 9860 KB Output is correct
18 Correct 99 ms 9888 KB Output is correct
19 Correct 86 ms 9884 KB Output is correct
20 Correct 184 ms 15212 KB Output is correct
21 Correct 136 ms 14996 KB Output is correct
22 Correct 137 ms 15132 KB Output is correct