oj.uz

Submission #159834

# Submission time Handle Problem Language Result Execution time Memory
159834 2019-10-25T01:18:32 Z qkxwsm Mechanical Doll (IOI18_doll) C++14
53 / 100
 261 ms 28152 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 270013
#define INF 998244353

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, T;
vi ord;
vi seq[2 * MAXN];
vi ans, ch[2];
int rv[2 * MAXN], arr[2 * MAXN];
int dif;

void build(int w, int L, int R)
{
	if (L == R)
	{
		L = rv[L];
		if (L < dif)
		{
			arr[w] = -1;
			return;
		}
		L -= dif;
		arr[w] = ord[L];
		//do smth
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
	arr[w] = -w;
}
void dfs(int w, int L, int R)
{
	if (L == R) return;
	ch[0][w - 1] = arr[w << 1];
	ch[1][w - 1] = arr[w << 1 | 1];
	int mid = (L + R) >> 1;
	dfs(w << 1, L, mid);
	dfs(w << 1 | 1, mid + 1, R);
}


void create_circuit(int n, vi A)
{
	n++; N = n;
	A.insert(A.begin(), 0);
	A.PB(0);
	M = SZ(A);
	FOR(i, 0, M - 1)
	{
		seq[A[i]].PB(A[i + 1]);
	}
	ans.resize(N);
	bool solve = false;
	FOR(i, 0, N)
	{
		if (seq[i].empty()) continue;
		if (SZ(seq[i]) == 1)
		{
			ans[i] = seq[i][0]; continue;
		}
		else if (SZ(seq[i]) == 2)
		{
			T++;
			ans[i] = -T;
			ch[0].PB(seq[i][0]);
			ch[1].PB(seq[i][1]);
			continue;
		}
		else
		{
			solve = true;
		}
	}
	if (solve)
	{
		ch[0].clear(); ch[1].clear();
		FOR(i, 0, N)
		{
			if (SZ(seq[i]) <= 1) continue;
			ans[i] = -1;
		}
		T = 0;
	}
	// ans[0] = A[1];
	// cerr << SZ(ans) << endl;
	FOR(i, 2, M)
	{
		if (SZ(seq[A[i - 1]]) == 1) continue;
		ord.PB(A[i]);
	}
	// for (int x : ord)
	// {
	// 	cerr << x << ' ';
	// }
	// cerr << endl;
	if (solve && SZ(ord) != 0)
	{
		int sz = 1;
		while(sz < SZ(ord)) sz *= 2;
		sz = 31 - __builtin_clz(sz);
		FOR(i, 0, (1 << sz))
		{
			int sum = 0;
			FOR(j, 0, sz)
			{
				if (i & (1 << j))
				{
					sum += (1 << (sz - 1 - j));
				}
			}
			rv[sum] = i;
			//reverse the
		}
		sz = (1 << sz);
		dif = sz - SZ(ord);
		ch[0].resize(sz - 1); ch[1].resize(sz - 1);
		build(1, 0, sz - 1);
		dfs(1, 0, sz - 1);
	}
	// assert(SZ(ch[0]) <= 2 * (SZ(A) - 2));
	// cerr << "SZ " << SZ(ch[0]) << endl;
	answer(ans, ch[0], ch[1]);
	//let's try for 100
	//build a segtree on ord. except we need to apply compression.
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12876 KB Output is correct
2 Correct 45 ms 16672 KB Output is correct
3 Correct 34 ms 16352 KB Output is correct
4 Correct 9 ms 12876 KB Output is correct
5 Correct 22 ms 14104 KB Output is correct
6 Correct 49 ms 18172 KB Output is correct
7 Correct 11 ms 12980 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12876 KB Output is correct
2 Correct 45 ms 16672 KB Output is correct
3 Correct 34 ms 16352 KB Output is correct
4 Correct 9 ms 12876 KB Output is correct
5 Correct 22 ms 14104 KB Output is correct
6 Correct 49 ms 18172 KB Output is correct
7 Correct 11 ms 12980 KB Output is correct
8 Correct 80 ms 19640 KB Output is correct
9 Correct 74 ms 19900 KB Output is correct
10 Correct 109 ms 23456 KB Output is correct
11 Correct 10 ms 12876 KB Output is correct
12 Correct 12 ms 12876 KB Output is correct
13 Correct 11 ms 12892 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12876 KB Output is correct
2 Correct 45 ms 16672 KB Output is correct
3 Correct 34 ms 16352 KB Output is correct
4 Correct 9 ms 12876 KB Output is correct
5 Correct 22 ms 14104 KB Output is correct
6 Correct 49 ms 18172 KB Output is correct
7 Correct 11 ms 12980 KB Output is correct
8 Correct 80 ms 19640 KB Output is correct
9 Correct 74 ms 19900 KB Output is correct
10 Correct 109 ms 23456 KB Output is correct
11 Correct 10 ms 12876 KB Output is correct
12 Correct 12 ms 12876 KB Output is correct
13 Correct 11 ms 12892 KB Output is correct
14 Incorrect 149 ms 28152 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12876 KB Output is correct
2 Correct 9 ms 12876 KB Output is correct
3 Correct 12 ms 12876 KB Output is correct
4 Correct 10 ms 12876 KB Output is correct
5 Correct 8 ms 12956 KB Output is correct
6 Correct 8 ms 12992 KB Output is correct
7 Correct 11 ms 12936 KB Output is correct
8 Correct 8 ms 12876 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 12876 KB Output is partially correct
2 Correct 84 ms 21040 KB Output is correct
3 Partially correct 118 ms 24424 KB Output is partially correct
4 Partially correct 111 ms 25276 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 12876 KB Output is partially correct
2 Correct 84 ms 21040 KB Output is correct
3 Partially correct 118 ms 24424 KB Output is partially correct
4 Partially correct 111 ms 25276 KB Output is partially correct
5 Partially correct 132 ms 27896 KB Output is partially correct
6 Partially correct 133 ms 27292 KB Output is partially correct
7 Partially correct 138 ms 27484 KB Output is partially correct
8 Partially correct 136 ms 26992 KB Output is partially correct
9 Partially correct 107 ms 25516 KB Output is partially correct
10 Partially correct 126 ms 27416 KB Output is partially correct
11 Partially correct 116 ms 26532 KB Output is partially correct
12 Partially correct 107 ms 25364 KB Output is partially correct
13 Correct 81 ms 22200 KB Output is correct
14 Partially correct 125 ms 25960 KB Output is partially correct
15 Partially correct 117 ms 26148 KB Output is partially correct
16 Partially correct 12 ms 13388 KB Output is partially correct
17 Correct 67 ms 21480 KB Output is correct
18 Correct 261 ms 21472 KB Output is correct
19 Partially correct 105 ms 25128 KB Output is partially correct
20 Partially correct 119 ms 26140 KB Output is partially correct
21 Partially correct 118 ms 26168 KB Output is partially correct
22 Partially correct 178 ms 25852 KB Output is partially correct