Submission #646224

#	Time	Username	Problem	Language	Result	Execution time	Memory
646224		slime	Mechanical Doll (IOI18_doll)	C++14	68.61 / 100	177 ms	30980 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> X, Y;
int sub = 0;

pair<bool, int> dfs(int node, int prv) { // fake id
  int S = X.size();
  int rr;
  bool gd = 1;
  if(X[node] >= -1) {
    rr = X[node];
  }
  else {
    pair<bool, int> left = dfs(-(X[node] + 1), node);
    gd &= left.first;
    rr = left.second;
  }
  if(Y[node] >= -1) {
    gd &= (rr == Y[node]);
  }
  else {
    pair<bool, int> right = dfs(-(Y[node] + 1), node);
    gd &= right.first;
    gd &= (rr == right.second);
  }
  if(gd && prv != -1) {
    if(-(X[prv] + 1) == node) X[prv] = rr;
    else Y[prv] = rr;
    sub++;
  }
  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;
  }
  
  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);

  
  X.resize((1 << layers) - 1);
  Y.resize((1 << layers) - 1);

  for(int i=0; i<(1 << layers) - 1; i++) {
    if(2*i+1 < (1<<layers) - 1) X[i] = -(2*i+1 + 1);
    if(2*i+2 < (1<<layers) - 1) Y[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";
      Y[cp] = sequence[i];
    }
    else {
      str += "X";
      X[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[-(X[i] + 1)] = par[-(Y[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(X[i] == Y[i]) {
      usable.push(i);
      used[i] = 0;
    }
    else if(usable.size()) {
      int ff = usable.front(); usable.pop();
      int gp = par[i];
      if(X[gp] == -(i+1)) X[gp] = -(ff+1);
      else Y[gp] = -(ff+1);
      X[ff] = X[i];
      Y[ff] = Y[i];
      used[i] = 0;
      used[ff] = 1;
      par[-(X[i] + 1)] = par[-(Y[i] + 1)] = ff;
      usable.push(i);
    }
  }

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

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'std::pair<bool, int> dfs(int, int)':
doll.cpp:16:7: warning: unused variable 'S' [-Wunused-variable]
   16 |   int S = X.size();
      |       ^

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