oj.uz

Submission #1032737

# Submission time Handle Problem Language Result Execution time Memory
1032737 2024-07-24T07:23:13 Z AmirAli_H1 Mechanical Doll (IOI18_doll) C++17
85.5537 / 100
 111 ms 66636 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 4;

int n, m, sz;
vector<int> ls[maxn];
vector<int> adj[maxn], Ax, A1, A2;

void solve(int v, vector<int> ls) {
	if (len(ls) == 0) {
		adj[v].pb(v);
		return ;
	}
	else {
		bool flag = 1; int val = ls[0];
		for (int i = 0; i < len(ls); i++) {
			if (ls[i] != val) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			adj[v].pb(ls[0]);
			return ;
		}
	}
	
	int u = sz++; adj[v].pb(u);
	int R = (1 << __lg(len(ls)));
	if (R != len(ls)) {
		R *= 2; int k = R - len(ls);
		vector<int> lsx;
		lsx.resize(R); fill(all(lsx), -1);
		while (k > 0) {
			int j = __builtin_ctz(k); k ^= (1 << j);
			int w = (R / (1 << j));
			for (int i = (w / 2); i < R; i += w) lsx[i] = u;
		}
		int j = 0;
		for (int i = 0; i < len(lsx); i++) {
			if (lsx[i] == -1) {
				lsx[i] = ls[j]; j++;
			}
		}
		ls = lsx;
	}
	
	vector<int> ls0, ls1;
	for (int i = 0; i < len(ls); i++) {
		if (i % 2 == 0) ls0.pb(ls[i]);
		else ls1.pb(ls[i]);
	}
	solve(u, ls0); solve(u, ls1);
}

void create_circuit(int Mx, vector<int> A) {
	m = Mx; n = len(A);
	ls[0].pb(A[0]);
	for (int i = 1; i < n; i++) {
		ls[A[i - 1]].pb(A[i]);
	}
	ls[A.back()].pb(0);
	
	sz = m + 1;
	for (int i = 0; i <= m; i++) {
		solve(i, ls[i]);
	}
	
	Ax.resize(m + 1); A1.resize(sz - m - 1); A2.resize(sz - m - 1);
	for (int i = 0; i <= m; i++) {
		int u = adj[i][0];
		if (u <= m) Ax[i] = u;
		else Ax[i] = -(u - m);
	}
	for (int i = m + 1; i < sz; i++) {
		int j = i - m - 1;
		int u1 = adj[i][0], u2 = adj[i][1];
		if (u1 <= m) A1[j] = u1;
		else A1[j] = -(u1 - m);
		if (u2 <= m) A2[j] = u2;
		else A2[j] = -(u2 - m);
	}
	
	answer(Ax, A1, A2);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 41 ms 54224 KB Output is correct
3 Correct 38 ms 52572 KB Output is correct
4 Correct 20 ms 47344 KB Output is correct
5 Correct 29 ms 51660 KB Output is correct
6 Correct 45 ms 55376 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 41 ms 54224 KB Output is correct
3 Correct 38 ms 52572 KB Output is correct
4 Correct 20 ms 47344 KB Output is correct
5 Correct 29 ms 51660 KB Output is correct
6 Correct 45 ms 55376 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct
8 Correct 62 ms 56924 KB Output is correct
9 Correct 60 ms 57724 KB Output is correct
10 Correct 77 ms 61764 KB Output is correct
11 Correct 20 ms 47196 KB Output is correct
12 Correct 20 ms 47164 KB Output is correct
13 Correct 20 ms 47288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 41 ms 54224 KB Output is correct
3 Correct 38 ms 52572 KB Output is correct
4 Correct 20 ms 47344 KB Output is correct
5 Correct 29 ms 51660 KB Output is correct
6 Correct 45 ms 55376 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct
8 Correct 62 ms 56924 KB Output is correct
9 Correct 60 ms 57724 KB Output is correct
10 Correct 77 ms 61764 KB Output is correct
11 Correct 20 ms 47196 KB Output is correct
12 Correct 20 ms 47164 KB Output is correct
13 Correct 20 ms 47288 KB Output is correct
14 Correct 103 ms 65324 KB Output is correct
15 Correct 59 ms 56256 KB Output is correct
16 Correct 82 ms 60904 KB Output is correct
17 Correct 20 ms 47192 KB Output is correct
18 Correct 20 ms 47196 KB Output is correct
19 Correct 19 ms 47320 KB Output is correct
20 Correct 101 ms 63312 KB Output is correct
21 Correct 20 ms 47196 KB Output is correct
22 Correct 19 ms 47412 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47392 KB Output is correct
2 Correct 21 ms 47404 KB Output is correct
3 Correct 25 ms 47312 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 19 ms 47288 KB Output is correct
6 Correct 20 ms 47196 KB Output is correct
7 Correct 20 ms 47192 KB Output is correct
8 Correct 20 ms 47352 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47244 KB Output is correct
2 Correct 40 ms 50860 KB Output is correct
3 Correct 33 ms 52928 KB Output is correct
4 Correct 38 ms 53680 KB Output is correct

Subtask #6
41.5537008656 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47244 KB Output is correct
2 Correct 40 ms 50860 KB Output is correct
3 Correct 33 ms 52928 KB Output is correct
4 Correct 38 ms 53680 KB Output is correct
5 Partially correct 111 ms 66636 KB Output is partially correct
6 Partially correct 110 ms 65916 KB Output is partially correct
7 Partially correct 111 ms 66004 KB Output is partially correct
8 Partially correct 110 ms 64528 KB Output is partially correct
9 Correct 72 ms 55300 KB Output is correct
10 Correct 93 ms 61888 KB Output is correct
11 Partially correct 95 ms 61780 KB Output is partially correct
12 Partially correct 68 ms 56660 KB Output is partially correct
13 Partially correct 78 ms 59236 KB Output is partially correct
14 Partially correct 77 ms 59504 KB Output is partially correct
15 Partially correct 75 ms 60032 KB Output is partially correct
16 Partially correct 21 ms 47704 KB Output is partially correct
17 Partially correct 68 ms 56596 KB Output is partially correct
18 Partially correct 66 ms 56344 KB Output is partially correct
19 Partially correct 73 ms 56648 KB Output is partially correct
20 Partially correct 96 ms 61644 KB Output is partially correct
21 Partially correct 98 ms 61268 KB Output is partially correct
22 Partially correct 93 ms 61100 KB Output is partially correct