Submission #1037433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037433		aaaaaarroz	Mechanical Doll (IOI18_doll)	C++17	100 / 100	249 ms	28060 KiB

doll

    #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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56