Submission #835241

#	Time	Username	Problem	Language	Result	Execution time	Memory
835241		Pablo_No	Mechanical Doll (IOI18_doll)	C++17	20 / 100	1070 ms	11836 KiB

doll

#include "doll.h"

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> st;
vector<pair<int, int>> S;

vector<int> constrv(int 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(k+(1 << d));
    }
    ans = nans;
  }

  return ans;
}

int constr(vector<int> rem)
{
  bool eq = true;
  for(int xx : rem) if(xx != rem[0])
      eq = false;
    
  if(eq)
  {
    //cerr << "*" << rem[0] << '\n';
    return rem[0];
  }
  ///

  vector<int> v1;
  vector<int> v2;

  for(int i = 0; i < rem.size(); i++)
  {
    if(i < rem.size()/2)
      v1.push_back(rem[i]);
    else
      v2.push_back(rem[i]);
  }

  int id = S.size();
  S.push_back({0, 0});

  int na = constr(v1);
  int nb = constr(v2);

  S[id] = {na, nb};

  return -id-1;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  st.assign(M+1, 0);

  vector<vector<int>> pos(M+1);

  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], pos[i][k-(p2-ni)]});
      //cerr << m[k] << '-' << pos[i][k-(p2-ni)] << '\n';
    }

    vector<int> toc(p2, -S.size()-1);

    sort(pm.begin(), pm.end());

    for(int i = 0; i < pm.size(); i++)
    {
      auto [aa, bb] = pm[i];
      //cerr << aa << '+' << bb << '\n';
      toc[aa] = bb;
    }

    st[i] = constr(toc);
  }

  st[0] = A[0];

  vector<int> X(S.size());
  vector<int> Y(S.size());

  for(int xx : st)
    //cerr << xx << '\n';

  for(int i = 0; i < S.size(); i++)
  {
    X[i] = S[i].first;
    Y[i] = S[i].second;
    //cerr << X[i] << ' ' << Y[i] << '\n';
  }

  answer(st, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int constr(std::vector<int>)':
doll.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0; i < rem.size(); i++)
      |                  ~~^~~~~~~~~~~~
doll.cpp:48:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if(i < rem.size()/2)
      |        ~~^~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:109: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]
  109 |     for(int i = 0; i < pm.size(); i++)
      |                    ~~^~~~~~~~~~~
doll.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int i = 0; i < S.size(); i++)
      |                  ~~^~~~~~~~~~
doll.cpp:124:11: warning: unused variable 'xx' [-Wunused-variable]
  124 |   for(int xx : st)
      |           ^~

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