oj.uz

답안 #1069023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069023 2024-08-21T14:33:50 Z Joshua_Andersson 자동 인형 (IOI18_doll) C++14
100 / 100
 121 ms 11856 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

const int inf = int(1e9);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

int n;
int ind = 1;
vi state;
vi x, y;
int k=0;
vi exitcnt;
int numexits = 0;
int build_tree(int d, vi& x, vi& y)
{
	int u = ind++;
	if (d==0)
	{
		exitcnt[u] = 2;
		numexits += 2;
		x[u] = inf;
		y[u] = inf;
		return u;
	}
	y[u] = build_tree(d - 1, x, y);
	x[u] = build_tree(d - 1, x, y);
	exitcnt[u] = exitcnt[x[u]] + exitcnt[y[u]];
	return u;
}

void killc(int u, vi& x, vi& y)
{
	if (u == inf) return;
	if (x[u]!=inf)
	{
		exitcnt[x[u]] = 0;
		killc(x[u], x, y);
		x[u] = inf;
	}
	if (y[u]!=inf)
	{
		exitcnt[y[u]] = 0;
		killc(y[u], x, y);
		y[u] = inf;
	}
}

bool kill(int u, vi& x, vi& y)
{
	if (u == inf) return false;
	if (numexits-exitcnt[u]>=n+1)
	{
		numexits -= exitcnt[u];
		killc(u, x, y);
		return true;
	}
	
	if (kill(x[u], x, y))
	{
		exitcnt[u] -= exitcnt[x[u]];
		x[u] = 1;
	}
	if (kill(y[u], x, y))
	{
		exitcnt[u] -= exitcnt[y[u]];
		y[u] = 1;
	}
	exitcnt[u] = 0;
	if (x[u] != inf) exitcnt[u] += exitcnt[x[u]];
	if (y[u] != inf) exitcnt[u] += exitcnt[y[u]];
	return false;
}

int* lastv = 0;
int statesum = 0;
void traverse(int u, int t)
{
	//cout << u << " ";
	int& v = state[u]?y[u]:x[u];
	if (v == -1) return;
	statesum += state[u] == 0 ? 1 : -1;
	state[u] ^= 1;
	if (v==inf)
	{
		lastv = &v;
		v = -t;
		return;
	}
	traverse(v, t);
}

void create_circuit(int m, std::vector<int> a)
{
	n = sz(a);
	vi c(m + 1, -1);
	c[0] = a[0];
	n--;
	a.erase(a.begin());
	while ((1<<(k+1))<=n)
	{
		k++;
	}

	state.resize(1 << (k+1));
	x.resize(1 << (k+1), inf);
	y.resize(1 << (k+1), inf);
	exitcnt.resize(1 << (k+1), 0);
	build_tree(k, x, y);
	kill(1, x, y);
	/*rep(i, sz(x))
	{
		if (x[i]!=inf) cout << (i) << " " << x[i] << "\n";
		if (y[i] != inf) cout << (i) << " " << y[i] << "\n";
	}*/
	rep(i, n)
	{
		traverse(1, a[i]);
		//cout << "\n";
	}
	repp(i, n, (1<<(k+1)))
	{
		traverse(1, -1);
		if (statesum == 0)
		{
			*lastv = 0;
			//cout << "ASD";
			break;
		}
		//cout << "\n";
	}

	while (x.back()==inf&&y.back()==inf)
	{
		x.pop_back();
		y.pop_back();
	}
	rep(i, sz(x)) x[i] *= -1, y[i] *= -1;
	rep(i, sz(x))
	{
		if (x[i] == -inf) x[i] = -1;
		if (y[i] == -inf) y[i] = -1;
	}
	x.erase(x.begin());
	y.erase(y.begin());
	/*int u = sz(x);
	rep(i, sz(x))
	{
		cout << -(i+1) << " " << x[i] << "\n";
		cout << -(i+1) << " " << y[i] << "\n";
	}*/
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 4540 KB Output is correct
3 Correct 37 ms 5204 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 1460 KB Output is correct
6 Correct 50 ms 6576 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 4540 KB Output is correct
3 Correct 37 ms 5204 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 1460 KB Output is correct
6 Correct 50 ms 6576 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 64 ms 7284 KB Output is correct
9 Correct 68 ms 9556 KB Output is correct
10 Correct 89 ms 11856 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 4540 KB Output is correct
3 Correct 37 ms 5204 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 1460 KB Output is correct
6 Correct 50 ms 6576 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 64 ms 7284 KB Output is correct
9 Correct 68 ms 9556 KB Output is correct
10 Correct 89 ms 11856 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 99 ms 11344 KB Output is correct
15 Correct 64 ms 8784 KB Output is correct
16 Correct 95 ms 11192 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 95 ms 11604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 59 ms 5556 KB Output is correct
3 Correct 56 ms 7508 KB Output is correct
4 Correct 92 ms 9040 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 59 ms 5556 KB Output is correct
3 Correct 56 ms 7508 KB Output is correct
4 Correct 92 ms 9040 KB Output is correct
5 Correct 120 ms 9808 KB Output is correct
6 Correct 96 ms 9764 KB Output is correct
7 Correct 96 ms 9756 KB Output is correct
8 Correct 92 ms 9448 KB Output is correct
9 Correct 64 ms 7504 KB Output is correct
10 Correct 90 ms 9436 KB Output is correct
11 Correct 93 ms 9184 KB Output is correct
12 Correct 70 ms 7508 KB Output is correct
13 Correct 55 ms 5716 KB Output is correct
14 Correct 62 ms 8008 KB Output is correct
15 Correct 65 ms 7984 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 64 ms 5592 KB Output is correct
18 Correct 53 ms 5456 KB Output is correct
19 Correct 61 ms 7504 KB Output is correct
20 Correct 100 ms 9248 KB Output is correct
21 Correct 100 ms 9044 KB Output is correct
22 Correct 121 ms 9188 KB Output is correct