Submission #835297

#	Time	Username	Problem	Language	Result	Execution time	Memory
835297		Pablo_No	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	96 ms	17000 KiB

doll

#include "doll.h"
  
#include <vector>
#include <algorithm>
#include <iostream>
  
using namespace std;

vector<int> X;
vector<int> Y;
  
vector<int> prec[50];
  
vector<int> constrv(int dep)
{
  if(!prec[dep].empty())
    return prec[dep];
  
  vector<int> ans(1, 0);
  
  for(int d = 0; d < dep; d++)
  {
    vector<int> nans;
    for(int k = 0; k < (1 << d); k++)
    {
      nans.push_back(ans[k]);
      nans.push_back(ans[k]+(1 << d));
    }
    ans = nans;
  }
  
  return prec[dep] = ans;
}
  
int constr(const vector<int>& rem, int l, int r)
{
  bool eq = true;
  for(int i = l; i <= r; i++) if(rem[i] != rem[l])
      eq = false;
    
  if(eq)
  {
    //cerr << "*" << rem[0] << '\n';
    return rem[l];
  }
  ///
  
  int id = X.size();
  X.push_back(0);
  Y.push_back(0);
  
  int na = constr(rem, l, l+(r-l+1)/2-1);
  int nb = constr(rem, l+(r-l+1)/2, r);
  
  X[id] = na;
  Y[id] = nb;
  
  return -id-1;
}

const int N = 2e5+5;

vector<int> pos[N];
  
void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  vector<int> st(M+1, 0);
  
  pos[0].push_back(A[0]);
  
  for(int i = 0; i < N-1; i++)
  {
    pos[A[i]].push_back(A[i+1]);
  }
  
  pos[A[N-1]].push_back(0);
  
  for(int i = 1; i <= M; i++) if(!pos[i].empty())
  {
    if(pos[i].size() == 1)
    {
      st[i] = pos[i][0];
      continue;
    }
  
    int ni = pos[i].size();
    int log = __builtin_clz(1)-__builtin_clz((int)pos[i].size()-1)+1;
    int p2 = (1 << log);
  
    vector<int> m = constrv(log);
  
    /*for(auto x : m)
      cerr << x << ' ';
    cerr << '\n';*/
  
    vector<pair<int, int>> pm;
    for(int k = p2-ni; k < p2; k++)
    {
      pm.push_back({m[k], k});
      //cerr << m[k] << '-' << pos[i][k-(p2-ni)] << '\n';
    }
  
    vector<int> toc(p2, -X.size()-1);
  
    sort(pm.begin(), pm.end());
  
    for(int k = 0; k < pm.size(); k++)
    {
      auto [aa, bb] = pm[k];
      //cerr << aa << '+' << bb << '\n';
      toc[bb] = pos[i][k];
    }
  
    /*for(int xx : toc)
      cerr << xx << ' ';
    cerr << '\n';*/
  
    st[i] = constr(toc, 0, toc.size()-1);
  }
  
  st[0] = A[0];
  
  answer(st, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int k = 0; k < pm.size(); k++)
      |                    ~~^~~~~~~~~~~

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