oj.uz

Submission #1093849

# Submission time Handle Problem Language Result Execution time Memory
1093849 2024-09-27T16:38:16 Z Nonoze Mechanical Doll (IOI18_doll) C++17
60.6719 / 100
 90 ms 14352 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;
map<int, int> unused;
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) {
		bool todo=0;
		if (!unused.count(mx)) {
			unused[mx]=-sz(x)-1, x.pb(base), y.pb(base), par.pb({prec, left});
			todo=1;
		}
		// cout << mx << ' ' << left << ' ' << prec << ' ' << unused[mx] << endl;
		if (prec<=0) ans[-prec]=unused[mx];
		else if (left) x[prec-1]=unused[mx];
		else y[prec-1]=unused[mx];
		if (todo && mx>2) {
			int s=-unused[mx];
			build(s, 1, mx/2, 0);
			build(s, 0, mx/2, 0);
		}
		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, a[0]);
	vector<int> nxt;
	for (int i=0; i<n; i++) nxt.pb(a[i]);
	nxt.pb(0);
	state.resize(2*n);
	if (sz(nxt)<2) ans[0]=(sz(nxt)?nxt[0]:0);
	else {
		int mx=1;
		while (mx<sz(nxt)) mx*=2;
		build(0, 1, mx, sz(nxt));
		for (auto u: nxt) simulate(-ans[0]-1, u);
	}
	for (auto &u: ans) u=ans[0];
	answer(ans, x, y);
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Partially correct 61 ms 8716 KB Output is partially correct
3 Partially correct 66 ms 8716 KB Output is partially correct
4 Partially correct 78 ms 13092 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Partially correct 61 ms 8716 KB Output is partially correct
3 Partially correct 66 ms 8716 KB Output is partially correct
4 Partially correct 78 ms 13092 KB Output is partially correct
5 Partially correct 88 ms 14352 KB Output is partially correct
6 Partially correct 85 ms 14108 KB Output is partially correct
7 Partially correct 87 ms 14112 KB Output is partially correct
8 Partially correct 82 ms 13988 KB Output is partially correct
9 Partially correct 63 ms 8516 KB Output is partially correct
10 Partially correct 90 ms 13720 KB Output is partially correct
11 Partially correct 83 ms 13392 KB Output is partially correct
12 Partially correct 63 ms 8852 KB Output is partially correct
13 Partially correct 66 ms 9268 KB Output is partially correct
14 Partially correct 70 ms 9268 KB Output is partially correct
15 Partially correct 67 ms 9528 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Correct 48 ms 8988 KB Output is correct
18 Partially correct 61 ms 8756 KB Output is partially correct
19 Partially correct 62 ms 8760 KB Output is partially correct
20 Partially correct 85 ms 13716 KB Output is partially correct
21 Partially correct 80 ms 13340 KB Output is partially correct
22 Partially correct 78 ms 13604 KB Output is partially correct