Submission #422743

#	Time	Username	Problem	Language	Result	Execution time	Memory
422743		alireza_kaviani	Mechanical Doll (IOI18_doll)	C++11	84 / 100	130 ms	11584 KiB

doll

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

const int MAXN = 3e5 + 10;

int cnt , ans[MAXN];
vector<int> vec , C , X , Y;

int reverse(int x){
	int ans = 0;
	for(int i = 0 ; i < cnt ; i++){
		ans = ans * 2 + ((x & (1 << i)) != 0);
	}
	return ans;
}

int solve(int ql , int qr , int l , int r){
	if(r <= ql || qr <= l)	return -1;
	if(r - l == 1)	return ans[l];
	int id = X.size();
	X.push_back(-1); Y.push_back(-1);
	int mid = l + r >> 1; 
	int a = solve(ql , qr , l , mid);
	int b = solve(ql , qr , mid , r);
	X[id] = a; Y[id] = b;
	return -(id + 1);
}

void create_circuit(int M, vector<int> A) {
	fill(ans , ans + MAXN , -1);
	int k = 1 , n = A.size();
	while(k < n)	k *= 2 , cnt++;
	for(int i = k - n ; i < k ; i++){
		vec.push_back(reverse(i));
	}
	sort(vec.begin() , vec.end());
	C.push_back(A[0]);
	for(int i = 0 ; i < n ; i++){
		ans[reverse(vec[i])] = (i + 1 < n ? A[i + 1] : 0);
	}
	for(int i = 0 ; i < M ; i++)	C.push_back(-1);
/*	for(int i = 0 ; i < k ; i++){
		cout << ans[i] << endl;
	}
*/	solve(k - n , k , 0 , k);
/*	for(int i : C)	cout << i << ' ';
	cout << endl;
	for(int i : X)	cout << i << ' ';
	cout << endl;
	for(int i : Y)	cout << i << ' ';
	cout << endl;*/
	answer(C , X , Y);
}

Compilation message (stderr)

doll.cpp: In function 'int solve(int, int, int, int)':
doll.cpp:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  int mid = l + r >> 1;
      |            ~~^~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56