Submission #1231065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231065		acoatoitgs	Mechanical Doll (IOI18_doll)	C++20	53 / 100	59 ms	13112 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<int>> con(M+1);
  for(ll i = 0; i < N; i++)
  {
    con[A[i]].emplace_back(A[i+1]);
  }

  int nx = -1;
  vector<int> X(2*N + 10), Y(2*N + 10);
  C[0] = A[0];

  auto solve = [&](ll pos) -> void
  {

    // cout << "\nSolving " << pos << "\n";

    if(con[pos].empty())
    {
      // cout << "No connection, going to " << 0 << "\n";
      C[pos] = 0;
      return;
    }

    if(con[pos].size() == 1)
    {
      // cout << "Single connection\n";
      C[pos] = con[pos][0];
      return;
    } 

    // cout << con[pos].size() << " " << __builtin_popcount(con[pos].size()) << " " << 
    // __bit_width((uint32_t)con[pos].size()) << "\n";

    int depth = (__builtin_popcount(con[pos].size()) == 1) ? 
    __bit_width((uint32_t)con[pos].size())-1 : 
    __bit_width((uint32_t)con[pos].size());
    
    int last = (1 << depth)-1;
    // cout << "Depth: " << depth << " last: " << last << "\n";
    int first_node = 0;
    
    function<int(ll, ll)> prop = [&](ll val, ll dep) -> int
    {
      int node = nx;
      nx--;
      if(dep == 0) first_node = node;

      int x,y;
      if(dep == depth-1)
      {
        ll val1 = val;
        ll val2 = val + (1 << dep);
        // cout << val1 << " " << val2 << " " << con[pos].size() << "\n";

        if(val1 < con[pos].size()-1)
        {
          x = con[pos][val1];
        }
        else if(val1 == last)
        {
          x = con[pos].back();
        }
        else
        {
          x = first_node;
        }

        if(val2 < con[pos].size()-1)
        {
          y = con[pos][val2];
        }
        else if(val2 == last)
        {
          y = con[pos].back();
        }
        else
        {
          y = first_node;
        }

      }
      else
      {
        x = prop(val, dep+1);
        y = prop(val + (1<<dep), dep+1);
      }
      // cout << "Setting " << -(node+1) << " to " << x << ", " << y << "\n";
      X[-(node+1)] = x;
      Y[-(node+1)] = y;

      return node;
    };  

    C[pos] = prop(0, 0);
  };

  for(int i = 1; i <= M; i++)
  {
    solve(i);
  } 
  X.resize(-(nx+1));
  Y.resize(-(nx+1));

  assert(-(nx+1) == X.size() && X.size() == Y.size());
  assert(C.size() == M+1);
  answer(C, X, Y);
}

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