Submission #1231190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231190		acoatoitgs	Mechanical Doll (IOI18_doll)	C++20	16 / 100	67 ms	13108 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
  {

    if(con[pos].empty())
    {
      C[pos] = 0;
      return;
    }

    if(con[pos].size() == 1)
    {
      C[pos] = con[pos][0];
      return;
    } 


    int depth = (__builtin_popcount(con[pos].size()) == 1) ? 
    __bit_width((uint32_t)con[pos].size())-1 : 
    __bit_width((uint32_t)con[pos].size());
    
    // cout << "DEPTH: " << depth << "\n";
    int last = (1 << depth)-1;
    int first_node = 0;
    
    vector<pair<ll,pair<ll, bool>>> tm;

    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);

        if(tm.size() < con[pos].size())
        {
          // cout << "Adding two vals\n";
          tm.push_back({val1, {node, 0}});
          tm.push_back({val2, {node, 1}});
        }
        else 
        {
          nx++;
          return first_node; 
        }
      }
      else
      {
        x = prop(val, dep+1);
        y = prop(val + (1<<dep), dep+1);

        X[-(node+1)] = x;
        Y[-(node+1)] = y;
      }
      // cout << "Returning " << node << "\n";
      return node;
    };  

    C[pos] = prop(0, 0);
    sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
    // cout << "Solving " << pos << "\n";
    // for(auto [a, b] : tm) cout << a << " " << b.first << " " << b.second << "\n";
    int sz = 0;
    while(sz < con[pos].size()-1)
    {
      auto [node, r] = tm.back().second;
      tm.pop_back();

      if(r)
      {
        Y[-(node+1)] = con[pos][sz];
      }
      else
      {
        X[-(node+1)] = con[pos][sz];
      }
      sz++;
    }

    while(tm.size() > 1)
    {
      auto [node, r] = tm.back().second;
      tm.pop_back();
      if(r)
      {
        Y[-(node+1)] = first_node;
      }
      else
      {
        X[-(node+1)] = first_node;
      }
    }

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

  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);

  using ld = long double;

  // ld score = 0;
  // ld lg = log2(N);
  // if(X.size() <= lg+N) score = 100;
  // else if (X.size() <= 2*N) score = 0.5 + 0.4*pow((ld)(2*N - X.size())/(ld)(N - lg), 2);
  // else score = 0;
  // cout << setprecision(3) << "SCORE: " << score << "\n";
  answer(C, X, Y);
}

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