Submission #1231237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231237		acoatoitgs	Mechanical Doll (IOI18_doll)	C++20	54.40 / 100	161 ms	327680 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()

void create_circuit(int M, vector<int> A) {
  int N = A.size();
  A.push_back(0);

  vector<int> C(M + 1);
  vector<vector<pair<int,int>>> con(M+1);
  for(ll i = 0; i < N; i++)
  {
    con[A[i]].emplace_back(i, A[i+1]);
  }

  int nx = -1;
  vector<int> X(2*N + 10), Y(2*N + 10);

  C[0] = A[0];  
  vector<pair<int,int>> nc;

  for(int i = 1; i <= M; i++)
  {
    if(con[i].size() == 0)
    {
      C[i] = 0;
    }
    else if(con[i].size() == 1)
    {
      C[i] = con[i][0].second;
    }
    else
    {
      C[i] = -1;
      for(auto e : con[i]) nc.emplace_back(e);
    }
  }  

  sort(all(nc), greater<pair<int,int>>());
  int len = nc.size();
  int depth = (__builtin_popcount(len) == 1) ? 
    __bit_width((uint32_t)len)-1 : 
    __bit_width((uint32_t)len);
  
  int first_node = -1;

  vector<pair<ll,pair<ll, bool>>> tm;
  function<int(int, int)> prop = [&](int val, int dep) -> int
  {
    int node = nx;
    nx--;
    if(dep == depth-1)
    {
      int val1 = val;
      int val2 = val + (1<<dep);
      
      if(tm.size() < len)
      {
        tm.push_back({val1, {node, 0}});
        tm.push_back({val2, {node, 1}});
        return node;
      }
      else
      {
        nx++;
        return first_node;
      }
    }
    else
    {
      int y = prop(val+(1<<dep), dep+1);
      int x = prop(val, dep+1);

      X[-(node+1)] = x;
      Y[-(node+1)] = y;
      return node;
    }
  };
  
  prop(0, 0);
  sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
  while(nc.size() != 1)
  {
    // cout << nc.back().first << " " << nc.back().second << " || " << tm.back().first << " " << tm.back().second.first << " " << tm.back().second.second<< "\n";
    int to = nc.back().second;
    nc.pop_back();
    
    auto [node, r] = tm.back().second;
    tm.pop_back();
    
    if(r) Y[-(node+1)] = to;
    else X[-(node+1)] = to;
  }

  while(tm.size() != 1)
  {
    // cout << "filling\n";
    auto [node, r] = tm.back().second;
    tm.pop_back();
    
    if(r) Y[-(node+1)] = -1;
    else X[-(node+1)] = -1;
  }

  // cout << "last:\n";
  // cout << nc.back().first << " " << nc.back().second << " || " << tm.back().first << " " << tm.back().second.first << " " << tm.back().second.second<< "\n";

  auto [node, r] = tm.back().second;
    
  if(r) Y[-(node+1)] = nc.back().second;
  else X[-(node+1)] = nc.back().second;

  X.resize(-(nx+1));
  Y.resize(-(nx+1));

  answer(C, X, Y);
}

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