oj.uz

Submission #1093807

# Submission time Handle Problem Language Result Execution time Memory
1093807 2024-09-27T14:51:40 Z Nonoze Mechanical Doll (IOI18_doll) C++17
60.402 / 100
 103 ms 16928 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, unused, base;
vector<int> a, ans, x, y, state, par;

void build(int prec, bool left, int mx, int nb) {
	if (mx==2) {
		if (nb==0) {
			if (unused==-1) {
				unused=-sz(x)-1;
				x.pb(base), y.pb(base);
			}
			if (prec<=0) ans[-prec]=unused;
			else if (left) x[prec-1]=unused;
			else y[prec-1]=unused;
			return;
		}
		else 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);
			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);
		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);
	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, a[0]);
	vector<vector<int>> nxt(m+1); nxt[0].pb(a[0]);
	for (int i=0; i<n; i++) nxt[a[i]].pb((i<n-1?a[i+1]:0));
	state.resize(2*n);
	for (int i=0; i<=m; i++) {
		if (sz(nxt[i])<2) { ans[i]=(sz(nxt[i])?nxt[i][0]:0); continue; }
		unused=-1, base=0;
		int mx=1;
		while (mx<sz(nxt[i])) mx*=2;
		build(-i, 1, mx, sz(nxt[i]));
		for (auto u: nxt[i]) simulate(-ans[i]-1, u);
	}
	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 7772 KB Output is correct
3 Correct 20 ms 6492 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 3928 KB Output is correct
6 Correct 21 ms 9564 KB Output is correct
7 Correct 1 ms 348 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 7772 KB Output is correct
3 Correct 20 ms 6492 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 3928 KB Output is correct
6 Correct 21 ms 9564 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 29 ms 9776 KB Output is correct
9 Correct 35 ms 11224 KB Output is correct
10 Correct 52 ms 15056 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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 7772 KB Output is correct
3 Correct 20 ms 6492 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 3928 KB Output is correct
6 Correct 21 ms 9564 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 29 ms 9776 KB Output is correct
9 Correct 35 ms 11224 KB Output is correct
10 Correct 52 ms 15056 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 57 ms 15424 KB Output is correct
15 Correct 28 ms 8524 KB Output is correct
16 Correct 46 ms 12872 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 50 ms 15076 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.8004944798 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 46 ms 8064 KB Output is correct
3 Partially correct 88 ms 10060 KB Output is partially correct
4 Partially correct 86 ms 13124 KB Output is partially correct

Subtask #6
33.6015383816 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 46 ms 8064 KB Output is correct
3 Partially correct 88 ms 10060 KB Output is partially correct
4 Partially correct 86 ms 13124 KB Output is partially correct
5 Partially correct 65 ms 16928 KB Output is partially correct
6 Partially correct 62 ms 16724 KB Output is partially correct
7 Partially correct 60 ms 16644 KB Output is partially correct
8 Partially correct 61 ms 16388 KB Output is partially correct
9 Partially correct 76 ms 9716 KB Output is partially correct
10 Partially correct 103 ms 15188 KB Output is partially correct
11 Partially correct 60 ms 16252 KB Output is partially correct
12 Partially correct 40 ms 10840 KB Output is partially correct
13 Partially correct 43 ms 11024 KB Output is partially correct
14 Partially correct 41 ms 11172 KB Output is partially correct
15 Partially correct 41 ms 11272 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Partially correct 35 ms 9476 KB Output is partially correct
18 Partially correct 33 ms 9444 KB Output is partially correct
19 Partially correct 34 ms 9944 KB Output is partially correct
20 Partially correct 49 ms 13792 KB Output is partially correct
21 Partially correct 59 ms 15056 KB Output is partially correct
22 Partially correct 44 ms 12980 KB Output is partially correct