oj.uz

Submission #1093863

# Submission time Handle Problem Language Result Execution time Memory
1093863 2024-09-27T20:46:21 Z Nonoze Mechanical Doll (IOI18_doll) C++17
100 / 100
 96 ms 17336 KB 
/*
*	Author: Nonoze
*	Created: Sunday 11/08/2024
*/
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

#ifndef _IN_LOCAL
	#define dbg(...)
#endif

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);}
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

// #define int long long
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;

int m, n, base=0;
vector<int> a, ans, x, y, state;
vector<pair<int, int>> par;

void build(int prec, bool left, int mx, int nb) {
	if (nb==0) {
		if (prec<=0) ans[-prec]=base;
		else if (left) x[prec-1]=base;
		else y[prec-1]=base;
		return;
	}
	if (mx==2) {
		if (nb==1) {
			if (prec<=0) ans[-prec]=-sz(x)-1;
			else if (left) x[prec-1]=-sz(x)-1;
			else y[prec-1]=-sz(x)-1;
			x.pb(base), y.pb(-inf), par.pb({prec, left});
			return;
		}
		if (prec<=0) ans[-prec]=-sz(x)-1;
		else if (left) x[prec-1]=-sz(x)-1;
		else y[prec-1]=-sz(x)-1;
		x.pb(-inf), y.pb(-inf), par.pb({prec, left});
		return;
	}
	if (prec<=0) ans[-prec]=-sz(x)-1;
	else if (left) x[prec-1]=-sz(x)-1;
	else y[prec-1]=-sz(x)-1;
	if (base==0) base=-sz(x)-1;
	x.pb(inf), y.pb(inf), par.pb({prec, left});
	int s=sz(x);
	build(s, 1, mx/2, max(0, nb-mx/2));
	build(s, 0, mx/2, min(nb, mx/2));
}


void simulate(int empl, int val) {
	int nxt=(state[empl]?y[empl]:x[empl]);
	if (nxt==-inf) {
		if (state[empl]) y[empl]=val;
		else x[empl]=val;
		state[empl]^=1;
		return;
	}
	nxt=-nxt-1;
	state[empl]^=1;
	simulate(nxt, val);
}

void create_circuit(int MM, vector<int> AA) { m=MM, a=AA, n=sz(a); ans.resize(m+1, inf); ans[0]=a[0];
	state.resize(2*n);
	vector<vector<int>> nxts(m+1);
	vector<bool> done(m+1, 0);
	for (int i=0; i<n; i++) nxts[a[i]].pb((i<n-1?a[i+1]:0));
	vector<int> nxt;
	int first=0;
	for (int i=1; i<n; i++) {
		if (sz(nxts[a[i-1]])>4) nxt.pb(a[i]), first=a[i-1];
	}
	if (sz(nxts[a.back()])>4) nxt.pb(0), first=a.back();
	for (int i=1; i<=m; i++) if (sz(nxts[i])<=4) {
		if (sz(nxts[i])<=1) {
			if (sz(nxts[i])==1) ans[i]=nxts[i][0];
			else ans[i]=0;
			continue;
		}
		base=0;
		int mx=1;
		while (mx<sz(nxts[i])) mx*=2;
		build(-i, 1, mx, sz(nxts[i]));
		for (auto u: nxts[i]) simulate(-ans[i]-1, u);
	}
	if (sz(nxt)>=2) {
		base=0;
		int mx=1;
		while (mx<sz(nxt)) mx*=2;
		build(-first, 1, mx, sz(nxt));
		for (auto u: nxt) simulate(-ans[first]-1, u);
	}
	for (auto &u: ans) if (u==inf) u=ans[first];
	// for (int i=0; i<=m; i++) {
	// 	cout << i << ' ' << ans[i] << endl;
	// }
	// for (int i=0; i<sz(x); i++) {
	// 	cout << -i-1 << ' ' << x[i] << ' ' << y[i] << endl;
	// }
	answer(ans, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 17 ms 7768 KB Output is correct
3 Correct 15 ms 6500 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 21 ms 9560 KB Output is correct
7 Correct 1 ms 352 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 17 ms 7768 KB Output is correct
3 Correct 15 ms 6500 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 21 ms 9560 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 33 ms 10152 KB Output is correct
9 Correct 31 ms 11484 KB Output is correct
10 Correct 47 ms 15560 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 1 ms 352 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 17 ms 7768 KB Output is correct
3 Correct 15 ms 6500 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 21 ms 9560 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 33 ms 10152 KB Output is correct
9 Correct 31 ms 11484 KB Output is correct
10 Correct 47 ms 15560 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 55 ms 17336 KB Output is correct
15 Correct 31 ms 9152 KB Output is correct
16 Correct 47 ms 14100 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 53 ms 15648 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 51 ms 8996 KB Output is correct
3 Correct 54 ms 9036 KB Output is correct
4 Correct 74 ms 13516 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 51 ms 8996 KB Output is correct
3 Correct 54 ms 9036 KB Output is correct
4 Correct 74 ms 13516 KB Output is correct
5 Correct 91 ms 16760 KB Output is correct
6 Correct 87 ms 16152 KB Output is correct
7 Correct 83 ms 16264 KB Output is correct
8 Correct 96 ms 15852 KB Output is correct
9 Correct 51 ms 9224 KB Output is correct
10 Correct 78 ms 14564 KB Output is correct
11 Correct 95 ms 15248 KB Output is correct
12 Correct 59 ms 10040 KB Output is correct
13 Correct 53 ms 10476 KB Output is correct
14 Correct 57 ms 10652 KB Output is correct
15 Correct 60 ms 10964 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 48 ms 9792 KB Output is correct
18 Correct 45 ms 10172 KB Output is correct
19 Correct 54 ms 9904 KB Output is correct
20 Correct 76 ms 15140 KB Output is correct
21 Correct 76 ms 14892 KB Output is correct
22 Correct 86 ms 14600 KB Output is correct