Submission #1222496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222496		zaki98	Mechanical Doll (IOI18_doll)	C++20	100 / 100	73 ms	13344 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define LOO(i,a,b) for (int i = a; i <=b;i++)
#define pii pair<int,int>
#define PB push_back
#define F first
typedef long long ll;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int curr = 0;
int getbigg(int n) {
  int num = 1 << (31 - __builtin_clz(n));
  if (num==n) return n;
  return 1 << (32 - __builtin_clz(n));
}
int maxydep = 0;

vector<pii> outgoers;
vector<vector<int>> depths(30);
bool build(int v, int l, int r, int m, int rii, int depth) {
  if (l==r) {
     if (l==0 || rii==r) {
       return true;
     }
      return false;
  }
  int mid = (l+r)/2;
  pii mhm = {-1,-1};
  if (build(2*v, l, mid, m, rii,depth+1)) {
    mhm.F = curr;
  }
  if (build(2*v+1, mid+1,r,m,rii,depth+1)) {
    mhm.second = curr;
  }
  if (mhm!=make_pair(-1,-1)) {
    maxydep = max(maxydep, depth);
    curr++;
    if (l+1==r) mhm = {-1,-1};
    if (mhm.F==-1||mhm.second==-1) {
      depths[depth].PB(curr);
    }
    outgoers.PB(mhm);
    return true;
  }
  return false;
}vector<bool> swpp;
vector<int> answ;
vector<int> gg;
int toppy;
bool traver(int smth, int l, int r) {
  int current = toppy;
  while (true) {
    if (swpp[current]) {
      swpp[current]=!swpp[current];
      if (outgoers[current].F==toppy) return false;
      if (l+1!=r) {
        r = (l+r)/2;
        current = outgoers[current].F;
      }
      else {
        outgoers[current].F = -gg[smth];
        return true;
      }
    }
    else {
      swpp[current]=!swpp[current];
      if (outgoers[current].second==toppy) return false;
      if (l+1!=r) {
        current = outgoers[current].second;
        l = (l+r)/2+1;
      }
      else {
        outgoers[current].second = -gg[smth];
        return true;
      }
    }
  }
}
void create_circuit(int m, std::vector<int> a) {
  if (a.size()==1) {
    answer({a[0], 0}, {}, {});
    return;
  }
  gg = a;
  gg.PB(0);
  int n = a.size();
  outgoers.PB({0,0});
  int upper2 = getbigg(n+1);
  build(1, 0, upper2-1, n-1, upper2-1,0);
  int progry = 0;
  toppy = curr;
  while (progry!=gg.size()) {
    for (int i = 29; i>=0;i--) {
      if (!depths[i].empty()) {
        if (i==maxydep) {
          progry++;
          if (outgoers[depths[i].back()].F==-1) {
            outgoers[depths[i].back()].F = depths[i].back();
          }
          else if (outgoers[depths[i].back()].second==-1) {
            outgoers[depths[i].back()].second = depths[i].back();
          }
          if (outgoers[depths[i].back()].F!=-1 && outgoers[depths[i].back()].second!=-1) {
            depths[i].pop_back();
          }
          break;
        }
        if (outgoers[depths[i].back()].F==-1) {
          curr++;
          outgoers[depths[i].back()].F=curr;
          depths[i+1].push_back(curr);
          outgoers.PB({-1,-1});
        }
        else if (outgoers[depths[i].back()].second==-1) {
          curr++;
          outgoers[depths[i].back()].second=curr;
          depths[i+1].push_back(curr);
          outgoers.PB({-1,-1});
        }
        if (outgoers[depths[i].back()].F!=-1 && outgoers[depths[i].back()].second!=-1) {
          depths[i].pop_back();
        }
        break;
      }
    }
  }
  for (auto &ele: outgoers) {
    if (ele.F==-1) ele.F=toppy;
    if (ele.second==-1) ele.second=toppy;
  }
  vector C(m+1, -toppy);
  swpp.assign(outgoers.size(), true);
  answ.assign(upper2, -1);
  int current = 0;
  LOO(i,0, upper2-1) {
    if (traver(current, 0, upper2-1)) {
      current++;
    }
  }
  vector<int> X((int)outgoers.size()-1), Y((int)(outgoers.size())-1);
  LOO(i,1,outgoers.size()-1) {
    X[i-1] = -outgoers[i].F;
    Y[i-1] = -outgoers[i].second;
  }
  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