Submission #416717

#	Time	Username	Problem	Language	Result	Execution time	Memory
416717		rumen_m	Mechanical Doll (IOI18_doll)	C++17	100 / 100	150 ms	12928 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int m,n;
 std::vector<int> C;
 int num;
 vector <int> X,Y;
 int times[400004];
 const int inf = 1e7;
 void solve(int v, int from, int to)
 {
    // cout<<v<<" "<<from<<" "<<to<<endl;
     X.push_back(-1);
     Y.push_back(-1);
   int mid = (from+to)/2;

   if(from<mid&&from<n)
   {
       num++;
       Y[v]=-num-1;
       solve(num,from,mid);
   }
   else
   {
        if(n<=from)Y[v] = inf;
        else
        Y[v]=-1;
   }

    if(mid+1<to&&mid+1<n)
   {
       num++;
       X[v]=-num-1;
       solve(num,mid+1,to);
   }
   else
   {if(n<=mid+1)X[v] = inf;
   else
       X[v]=-1;
   }

    return ;
 }
void create_circuit(int _M, std::vector<int> _A) {
  a = _A;
  a.push_back(0);
   n = a.size();
  m = _M;
 C.resize(m+1);
  C[0] = -1;
  for (int i = 1; i <= m; ++i) {
    C[i] = -1;
  }
int br = 1;
while(br<n)br*=2;
  solve(0, 0, br-1);
 int c = 0;

 int x = 0;
 while(c<n)
 {
     times[x]++;
     if(times[x]%2==1)
     {
         if(X[x]==-1)
         {
             X[x] = a[c];
             c++;
             x = 0;
         }
         else
         {
             x = -X[x]-1;
         }

     }
     else
     {
         if(Y[x]==-1)
         {
             Y[x] = a[c];
             c++;
             x = 0;
         }
         else
         {
             x = -Y[x]-1;
         }
     }
     if(x==-inf-1)x=0;

 } //for(int i=0;i<=num;i++)
/// {
///cout<<i<<": "<<X[i]<<" "<<Y[i]<<endl;
 //}
for(int i=0;i<=num;i++)
 {
if(X[i]==inf)X[i] = -1;
if(Y[i]==inf)Y[i]=-1;
 }
//cout<<"YEs"<<endl;
  answer(C, X, Y);
}
/*#include <bits/stdc++.h>

using namespace std;

void answer(vector<int> C, vector<int> X, vector<int> Y);

vector<int> C, X, Y;

const int _N = 1e6 + 7;

int B[_N][2], timer[_N], cnt, n, m, k = 0;

int f(int s, int e){
	if(n <= s){
		return 1;
	}
	if(s == e){
		return -1;
	}

	int m = (s + e) / 2, c = ++k;

	B[c][1] = f(s, m);
	B[c][0] = f(m + 1, e);

	return c;
}

void create_circuit(int M, vector<int> A){
	for(int i = 0; i < M; i++){
		C.push_back(-1);
	}
	C.push_back(-1);

	A.push_back(0);

	n = (int)A.size();
	m = M;

	int t = 1;
	while(t < n){
		t *= 2;
	}

	f(0, t - 1);

	for(int i = 1, c = 0; c < n;){
		int &x = B[i][timer[i] & 1];
		++timer[i];

		if(x < 0){
			x = -A[c++];
			i = 1;
			continue;
		}

		i = x;
	}

	for(int i = 1; i <= k; i++){
		X.push_back(-B[i][0]);
		Y.push_back(-B[i][1]);
	}
  for(int i=0;i<X.size();i++)
 {
cout<<i<<": "<<X[i]<<" "<<Y[i]<<endl;
 }
	answer(C, X, Y);
}
*/

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