oj.uz

Submission #1093853

# Submission time Handle Problem Language Result Execution time Memory
1093853 2024-09-27T17:07:24 Z Nonoze Mechanical Doll (IOI18_doll) C++17
72.6719 / 100
 101 ms 19528 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;
		}
		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, inf); ans[0]=a[0];
	vector<vector<int>> nxts(m+1);
	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]])>1) nxt.pb(a[i]), first=a[i-1];
		else ans[a[i-1]]=a[i];
	}
	if (sz(nxts[a.back()])>1) nxt.pb(0), first=a.back();
	else ans[a.back()]=0;
	state.resize(2*n);
	if (sz(nxt)>=2) {
		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 348 KB Output is correct
2 Correct 18 ms 7760 KB Output is correct
3 Correct 15 ms 6492 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3928 KB Output is correct
6 Correct 24 ms 9660 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 7760 KB Output is correct
3 Correct 15 ms 6492 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3928 KB Output is correct
6 Correct 24 ms 9660 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 61 ms 12880 KB Output is correct
9 Correct 54 ms 13132 KB Output is correct
10 Incorrect 101 ms 19528 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 7760 KB Output is correct
3 Correct 15 ms 6492 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3928 KB Output is correct
6 Correct 24 ms 9660 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 61 ms 12880 KB Output is correct
9 Correct 54 ms 13132 KB Output is correct
10 Incorrect 101 ms 19528 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 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
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Correct 50 ms 8932 KB Output is correct
3 Partially correct 63 ms 8992 KB Output is partially correct
4 Partially correct 81 ms 13608 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 Correct 50 ms 8932 KB Output is correct
3 Partially correct 63 ms 8992 KB Output is partially correct
4 Partially correct 81 ms 13608 KB Output is partially correct
5 Partially correct 99 ms 16768 KB Output is partially correct
6 Partially correct 94 ms 16140 KB Output is partially correct
7 Partially correct 96 ms 16424 KB Output is partially correct
8 Partially correct 95 ms 15632 KB Output is partially correct
9 Partially correct 64 ms 8972 KB Output is partially correct
10 Partially correct 81 ms 14560 KB Output is partially correct
11 Partially correct 83 ms 15244 KB Output is partially correct
12 Partially correct 62 ms 10040 KB Output is partially correct
13 Correct 56 ms 10476 KB Output is correct
14 Partially correct 72 ms 10808 KB Output is partially correct
15 Partially correct 76 ms 10960 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 51 ms 9796 KB Output is correct
18 Correct 48 ms 9928 KB Output is correct
19 Partially correct 66 ms 9840 KB Output is partially correct
20 Partially correct 85 ms 15148 KB Output is partially correct
21 Partially correct 83 ms 14888 KB Output is partially correct
22 Partially correct 81 ms 14592 KB Output is partially correct