oj.uz

Submission #1035680

# Submission time Handle Problem Language Result Execution time Memory
1035680 2024-07-26T13:34:22 Z 0npata Mechanical Doll (IOI18_doll) C++17
90 / 100
 1000 ms 36240 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int long long

#define EMPTY 0
#define dbg(v)                                                                 \
	cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

void create_circuit(int32_t M, std::vector<int32_t> A) {
	//cerr << "HELLO" << '\n';
	int N = A.size();
	map<int, int> X, Y;

	int hb = -1;
	for(int i = 0; i<32; i++) {
		if(N & 1ll << i) hb = i;
	}
	assert(hb != -1);

	std::vector<int32_t> C(M + 1, -hb-1);
	int si = hb+2;

	//dbg(hb);

	auto tree = [&](int sz) {
		for(int i = 1; i<sz/2; i++) {
			X[i+si-1] = -(i*2 + si - 1);
			Y[i+si-1] = -(i*2 + 1 + si -1);
		}
		si += sz-1;
	};

	for(int i = hb+1; i>=1; i--) {
		if((1ll<<(i-1)) & N) {
			if(i > 1) {
				X[i] = -si;
				tree(1ll << (i-1));
			}
		}
		else {
			X[i] = -hb-1;
		}
		Y[i] = -i + 1;
		//cerr << X[i] << ' ';
	}
	//cerr << '\n';

	vec<bool> state(N*3+10, false);

	vec<int32_t> a = A;
	a.push_back(1e9);
	int i = 0;

	int cur = 0;
	int cnt = 0;
	do {
		cnt++;
		//cerr << cur << '\n';
		int nxt;
		if(cur < 0) {
			state[-cur] = !state[-cur];
			if(state[-cur]) {
				if(X.count(-cur) == 0) {
					X[-cur] = a[i++];
				}
				nxt = X[-cur];
			}
			else {
				if(Y.count(-cur) == 0) {
					Y[-cur] = a[i++];
				}
				nxt = Y[-cur];
			}
		}
		else {
			nxt = C[cur];
		}
		//if(cnt > 15) break;
		cur = nxt;
	} while(cur != 0);

	int S = si;
	vec<int32_t> XA(si-1, 1e9);
	vec<int32_t> YA(si-1, 1e9);

	for(auto [i, val] : X) {
		XA[i-1] = val;
	}
	for(auto [i, val] : Y) {
		YA[i-1] = val;
	}


	answer(C, XA, YA);
}

Compilation message

doll.cpp: In function 'void create_circuit(int32_t, std::vector<int>)':
doll.cpp:85:6: warning: unused variable 'S' [-Wunused-variable]
   85 |  int S = si;
      |      ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 234 ms 12520 KB Output is correct
3 Correct 208 ms 12352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 367 ms 18684 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 234 ms 12520 KB Output is correct
3 Correct 208 ms 12352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 367 ms 18684 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 599 ms 23884 KB Output is correct
9 Correct 550 ms 24196 KB Output is correct
10 Correct 917 ms 36240 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 234 ms 12520 KB Output is correct
3 Correct 208 ms 12352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 367 ms 18684 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 599 ms 23884 KB Output is correct
9 Correct 550 ms 24196 KB Output is correct
10 Correct 917 ms 36240 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 965 ms 35944 KB Output is correct
15 Correct 568 ms 23484 KB Output is correct
16 Execution timed out 1018 ms 32064 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 436 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 1 ms 344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 648 ms 22452 KB Output is correct
3 Correct 621 ms 22608 KB Output is correct
4 Correct 920 ms 34332 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 648 ms 22452 KB Output is correct
3 Correct 621 ms 22608 KB Output is correct
4 Correct 920 ms 34332 KB Output is correct
5 Correct 899 ms 35448 KB Output is correct
6 Correct 869 ms 35352 KB Output is correct
7 Correct 873 ms 35332 KB Output is correct
8 Correct 870 ms 35100 KB Output is correct
9 Correct 520 ms 22600 KB Output is correct
10 Correct 849 ms 34860 KB Output is correct
11 Correct 891 ms 34600 KB Output is correct
12 Correct 581 ms 22848 KB Output is correct
13 Correct 535 ms 23116 KB Output is correct
14 Correct 544 ms 23364 KB Output is correct
15 Correct 582 ms 23368 KB Output is correct
16 Correct 9 ms 1116 KB Output is correct
17 Correct 524 ms 22804 KB Output is correct
18 Correct 529 ms 22784 KB Output is correct
19 Correct 569 ms 22856 KB Output is correct
20 Correct 930 ms 34848 KB Output is correct
21 Correct 859 ms 34588 KB Output is correct
22 Correct 881 ms 34556 KB Output is correct