oj.uz

Submission #1093864

# Submission time Handle Problem Language Result Execution time Memory
1093864 2024-09-27T20:55:23 Z Nonoze Mechanical Doll (IOI18_doll) C++17
100 / 100
 79 ms 15156 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 base=0;
vector<int> 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==1) {
		if (prec<=0) ans[-prec]=-inf;
		else if (left) x[prec-1]=-inf;
		else y[prec-1]=-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, 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 m, vector<int> a) { int n=sz(a); ans.resize(m+1, inf); a.pb(0);
	state.resize(2*n);

	int mx=1;
	while (mx<sz(a)) mx*=2;
	build(0, 1, mx, sz(a));
	for (auto u: a) simulate(-ans[0]-1, u);

	for (auto &u: ans) if (u==inf) u=ans[0];
	answer(ans, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 29 ms 5804 KB Output is correct
3 Correct 27 ms 5336 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 5 ms 1480 KB Output is correct
6 Correct 37 ms 8256 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 348 KB Output is correct
2 Correct 29 ms 5804 KB Output is correct
3 Correct 27 ms 5336 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 5 ms 1480 KB Output is correct
6 Correct 37 ms 8256 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 52 ms 9628 KB Output is correct
9 Correct 53 ms 10128 KB Output is correct
10 Correct 74 ms 15156 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 0 ms 352 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 29 ms 5804 KB Output is correct
3 Correct 27 ms 5336 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 5 ms 1480 KB Output is correct
6 Correct 37 ms 8256 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 52 ms 9628 KB Output is correct
9 Correct 53 ms 10128 KB Output is correct
10 Correct 74 ms 15156 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 0 ms 352 KB Output is correct
14 Correct 75 ms 14572 KB Output is correct
15 Correct 55 ms 9096 KB Output is correct
16 Correct 79 ms 14124 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 77 ms 14608 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 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 440 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 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 50 ms 8140 KB Output is correct
3 Correct 51 ms 8136 KB Output is correct
4 Correct 67 ms 12748 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 50 ms 8140 KB Output is correct
3 Correct 51 ms 8136 KB Output is correct
4 Correct 67 ms 12748 KB Output is correct
5 Correct 74 ms 13960 KB Output is correct
6 Correct 73 ms 13616 KB Output is correct
7 Correct 70 ms 13632 KB Output is correct
8 Correct 68 ms 13360 KB Output is correct
9 Correct 50 ms 8184 KB Output is correct
10 Correct 68 ms 13288 KB Output is correct
11 Correct 69 ms 13176 KB Output is correct
12 Correct 50 ms 8388 KB Output is correct
13 Correct 52 ms 8648 KB Output is correct
14 Correct 53 ms 8896 KB Output is correct
15 Correct 55 ms 8900 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 46 ms 8780 KB Output is correct
18 Correct 53 ms 8388 KB Output is correct
19 Correct 53 ms 8384 KB Output is correct
20 Correct 71 ms 13208 KB Output is correct
21 Correct 70 ms 13080 KB Output is correct
22 Correct 70 ms 13100 KB Output is correct