oj.uz

Submission #1037433

# Submission time Handle Problem Language Result Execution time Memory
1037433 2024-07-28T21:01:09 Z aaaaaarroz Mechanical Doll (IOI18_doll) C++17
100 / 100
 249 ms 28060 KB 
    #include "doll.h"
    #include<bits/stdc++.h>
    using namespace std;
    #define vec vector
    #define int long long
    #define map unordered_map
     
    #define EMPTY 0         
    void create_circuit(int32_t M, std::vector<int32_t> A) {
    	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;
    	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;
    	}
    	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++;
    		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];
    		}
    		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:67:10: warning: unused variable 'S' [-Wunused-variable]
   67 |      int S = si;
      |          ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 61 ms 9836 KB Output is correct
3 Correct 59 ms 9184 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 99 ms 14588 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 61 ms 9836 KB Output is correct
3 Correct 59 ms 9184 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 99 ms 14588 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 127 ms 17716 KB Output is correct
9 Correct 128 ms 18056 KB Output is correct
10 Correct 212 ms 28060 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 61 ms 9836 KB Output is correct
3 Correct 59 ms 9184 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 99 ms 14588 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 127 ms 17716 KB Output is correct
9 Correct 128 ms 18056 KB Output is correct
10 Correct 212 ms 28060 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 436 KB Output is correct
14 Correct 223 ms 27572 KB Output is correct
15 Correct 127 ms 17204 KB Output is correct
16 Correct 228 ms 27548 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 226 ms 27904 KB Output is correct
21 Correct 0 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 1 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 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 344 KB Output is correct
2 Correct 124 ms 16948 KB Output is correct
3 Correct 124 ms 16916 KB Output is correct
4 Correct 228 ms 26904 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 124 ms 16948 KB Output is correct
3 Correct 124 ms 16916 KB Output is correct
4 Correct 228 ms 26904 KB Output is correct
5 Correct 220 ms 27352 KB Output is correct
6 Correct 222 ms 27348 KB Output is correct
7 Correct 221 ms 27292 KB Output is correct
8 Correct 211 ms 27028 KB Output is correct
9 Correct 119 ms 17048 KB Output is correct
10 Correct 210 ms 27064 KB Output is correct
11 Correct 215 ms 26772 KB Output is correct
12 Correct 119 ms 16948 KB Output is correct
13 Correct 124 ms 17096 KB Output is correct
14 Correct 131 ms 16956 KB Output is correct
15 Correct 126 ms 17204 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 124 ms 16840 KB Output is correct
18 Correct 122 ms 16784 KB Output is correct
19 Correct 119 ms 16788 KB Output is correct
20 Correct 218 ms 27000 KB Output is correct
21 Correct 249 ms 27028 KB Output is correct
22 Correct 224 ms 27028 KB Output is correct