Submission #421643

#	Time	Username	Problem	Language	Result	Execution time	Memory
421643		marcipan5000	Mechanical Doll (IOI18_doll)	C++14	6 / 100	107 ms	13988 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> t[100001];
vector<int> c,x,y;
int p=-1;
int g;
int s;

int rev(int q,int w) {
  int ans=0;
  for (int i=0;i<q;i++) {
    if ((w>>i)%2==1) {
      ans=(ans^(1<<(q-i-1)));
    }
  }
  return(ans);
}

int build(int a,int b,int r,int z) {
  if (a==b) {
    return(t[z][rev(r,a)]);
  }
  int x1,y1;
  x1=build(a,(a+b)/2,r,z);
  y1=build((a+b)/2+1,b,r,z);
  /* cout << a << " " << b << " " << r << " " << z << " " << x1 << " " << y1 << endl; */
  if (x1!=y1) {
    int p2=p; p--;
    x[-1*p2-1]=x1;
    y[-1*p2-1]=y1;
    return(p2);
  }
  return(x1);
}

void create_circuit (int M, std::vector<int> A) {
    int n=A.size();

    for (int i=0;i<n-1;i++) {
        t[A[i]].push_back(A[i+1]);
    }

    t[A[n-1]].push_back(0);
    t[0].push_back(A[0]);
    
    x.resize(400000);
    y.resize(400000);

    for (int i=0;i<=M;i++) {
        if (t[i].size()==0) {
          c.push_back(0);
        }
        if (t[i].size()==1) {
          c.push_back(t[i][0]);
        }
        if (t[i].size()>1) {
          g=pow(2,int(log2(int(t[i].size())-1))+1);
          s=t[i].size()-1;
          t[i].resize(g);
          t[i][g-1]=t[i][s];
          for (int j=s;j<g-1;j++) {
            t[i][j]=p;
          }
          c.push_back(build(0,g-1,int(log2(g)),i));
        }
    }
    
    x.resize(-1*p-1);
    y.resize(-1*p-1);

    answer(c,x,y);
}

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