Submission #646232

#	Time	Username	Problem	Language	Result	Execution time	Memory
646232		slime	Mechanical Doll (IOI18_doll)	C++14	20 / 100	127 ms	15064 KiB

doll

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

void create_circuit(int M, std::vector<int> A);

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

int lg(int x) {
  return 32 - __builtin_clz(x) - 1;
}
vector<int> tempX, tempY;

pair<bool, int> dfs(int node, int prv) { // fake id
  int rr;
  bool gd = 1;
  if(tempX[node] >= -1) {
    rr = tempX[node];
  }
  else {
    pair<bool, int> left = dfs(-(tempX[node] + 1), node);
    gd &= left.first;
    rr = left.second;
  }
  if(tempY[node] >= -1) {
    gd &= (rr == tempY[node]);
  }
  else {
    pair<bool, int> right = dfs(-(tempY[node] + 1), node);
    gd &= right.first;
    gd &= (rr == right.second);
  }
  if(gd && prv != -1) {
    if(-(tempX[prv] + 1) == node) tempX[prv] = rr;
    else tempY[prv] = rr;
  }
  return {gd, rr};
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  int freq[M + 1];
  for(int i=0; i<=M; i++) freq[i] = 0;
  for(int i=0; i<N; i++) freq[A[i]]++;
  freq[0]++;
  vector<int> C(M + 1);
  for(int i=0; i<=M; i++) C[i] = 0;
  C[0] = A[0];
  vector<int> sequence;
  for(int i=0; i<N; i++) {
    if(freq[A[i]] == 1) {
      C[A[i]] = (i+1 == N ? 0 : A[i+1]);
    }
    else {
      sequence.push_back((i+1 == N ? 0 : A[i+1]));
      C[A[i]] = -1;
    }
  }

  if(sequence.empty()) {
    answer(C, sequence, sequence);
    return;
  }
  // Actual problem

  vector<int> list[M+1];
  for(int i=0; i<N; i++) {
    list[A[i]].push_back(i);
  }

  vector<int> X, Y;

  for(int element=1; element<=M; element++) {
    if(freq[element] == 1) continue;
    sequence.clear();
    tempX.clear();
    tempY.clear();
    for(int x: list[element]) {
      sequence.push_back((x+1 == N ? 0 : A[x+1]));
    }
  
    int len = sequence.size();

    while((1 << lg(len)) != len) {
      sequence.push_back(-1);
      swap(sequence[sequence.size() - 2], sequence[sequence.size() - 1]);
      len++;
    }

    len = sequence.size();
    int cnt = 0;
    for(int x: sequence) cnt += (x == -1);

    vector<int> cpy = sequence;
    vector<int> ord;
    for(int x: sequence) if(x != -1) ord.push_back(x);
    int id = 0;
    for(int i=0; i<len; i++) {
      if(i%2 == 1 && cnt > 0) {
        cnt--;
        sequence[i] = -1;
      }
      else {
        sequence[i] = ord[id++];
      }
    }

    //for(int x: sequence) cout << x << " ";
    //cout << "\n";

    int layers = lg(len);

    
    tempX.resize((1 << layers) - 1);
    tempY.resize((1 << layers) - 1);

    for(int i=0; i<(1 << layers) - 1; i++) {
      if(2*i+1 < (1<<layers) - 1) tempX[i] = -(2*i+1 + 1);
      if(2*i+2 < (1<<layers) - 1) tempY[i] = -(2*i+2 + 1);
    }
    for(int i=0; i<len; i++) {
      int cp = 0;
      string str;
      for(int j=0; j<lg(len)-1; j++) {
        if(i & (1<<j)) {
          cp = cp * 2 + 2;
          str += "Y";
        }
        else {
          cp = cp * 2 + 1;
          str += "X";
        }
      }
      if(i & (1 << (lg(len) - 1))) {
        str += "Y";
        tempY[cp] = sequence[i];
      }
      else {
        str += "X";
        tempX[cp] = sequence[i];
      }
      //cout << cp << " " << str << "\n";
    }
    
    dfs(0, -1);

    queue<int> usable;
    unordered_map<int, int> par;
    for(int i=0; i<(1<<layers)-1; i++) par[-(tempX[i] + 1)] = par[-(tempY[i] + 1)] = i;

    bool used[(1<<layers) - 1];
    for(int i=0; i<(1<<layers)-1; i++) used[i] = 1;
    for(int i=0; i<(1<<layers)-1; i++) {
      if(tempX[i] == tempY[i]) {
        usable.push(i);
        used[i] = 0;
      }
      else if(usable.size()) {
        int ff = usable.front(); usable.pop();
        int gp = par[i];
        if(tempX[gp] == -(i+1)) tempX[gp] = -(ff+1);
        else tempY[gp] = -(ff+1);
        tempX[ff] = tempX[i];
        tempY[ff] = tempY[i];
        used[i] = 0;
        used[ff] = 1;
        par[-(tempX[i] + 1)] = par[-(tempY[i] + 1)] = ff;
        usable.push(i);
      }
    }

    for(int i=(1<<layers)-2; i>=0; i--) {
      if(!used[i]) {
        tempX.pop_back();
        tempY.pop_back();
      }
    }

    X = tempX;
    Y = tempY;
  }
  

  answer(C, X, Y);
}

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