Submission #1231547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231547		acoatoitgs	자동 인형 (IOI18_doll)	C++20	100 / 100	59 ms	14008 KiB

doll

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

#define ll int
#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);
  bitset<100005> uniq;
  bitset<100005> seen;
  vector<int> X(2*N + 500), Y(2*N + 500);
  vector<pair<ll,pair<ll, bool>>> tm;
  
  fill(all(C), 0);
  C[0] = A[0];  
  uniq.flip();
  if(N == 1)
  {
    answer(C, {}, {});
    return;
  }
  for(ll i = 0; i < N; i++)
  {
    if(seen[A[i]]) uniq[A[i]] = 0;
    seen[A[i]] = 1;
  }
  int len = 0;
  int nx = -1;

  for(int i = 0; i < N; i++) 
  {
    len += (!uniq[A[i]]);
  }
  for(int i = 1; i <= M; i++)
  {
    if(!seen[i]) C[i] = 0;
  }

  if(len == 0)
  {
    for(int i = 0; i < N; i++) C[A[i]] = A[i+1];
    answer(C, {}, {});
    return;
  }
  // cout << "LEN: " << len << "\n";
  // cout << "LEN: " <<  len << "\n";


  int depth = max((unsigned int)1, (unsigned int)((__builtin_popcount(len) == 1) ? 
    __bit_width((uint32_t)len)-1 : 
    __bit_width((uint32_t)len)));
  
  int first_node = -1;
  // cout << depth << " " << first_node << "\n";
  function<int(int, int)> prop = [&](int val, int dep) -> int
  {
    // cout << val << " " << dep << "\n";
    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 = -1;
      if(tm.size() < len)
        x = prop(val, dep+1);

      X[-(node+1)] = x;
      Y[-(node+1)] = y;
      return node;
    }
  };
  prop(0, 0);
  
  // cout << "SZ:: " << nx << "\n";
  // cout << "SZ: " << tm.size() << "\n";
  sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
  int idx = 0;
  while(len > 1 && idx < N)
  {
    if(uniq[A[idx]])
    {
      C[A[idx]] = A[idx+1];
      idx++;
      continue;
    }
    else C[A[idx]] = first_node;
    int to = A[idx+1];

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

  while(idx < N)
  {
    // cout << "In: " << idx << " " << uniq[A[idx]] << " " << tm.size() << "\n";
    if(uniq[A[idx]])
    {
      C[A[idx]] = A[idx+1];
      idx++;
      continue;
    }
    else C[A[idx]] = first_node;
    int to = A[idx+1];

    auto [node, r] = tm.back().second;
    tm.pop_back();
    
    if(r) Y[-(node+1)] = to;
    else X[-(node+1)] = to;
    idx++;
    len--;
  }

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

  answer(C, X, Y);
}

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