제출 #1038042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038042		Mr_Husanboy	자동 인형 (IOI18_doll)	C++17	39 / 100	79 ms	14140 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
 
template<typename T>
int len(T &a){
  return a.size();
}
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
 
void create_circuit(int m, vector<int> a) {
  int n = a.size();
  vector<int> c(m + 1);
  a.push_back(0);
  c[0] = a[0];
  vector<vector<int>> pos(m + 1);
  for(int i = 0; i < n; i ++){
    pos[a[i]].push_back(i);
  }
 
  vector<int> x, y;
 
  auto addx = [&](int from, int to)->void{
    while(len(x) < -from) x.push_back(0);
    x[-from - 1] = to;
  };
  auto addy = [&](int from, int to)->void{
    while(len(y) < -from) y.push_back(0);
    y[-from - 1] = to;
  };
 
  for(int i = 1; i <= m; i ++){
    if(len(pos[i]) == 0) continue;
    if(len(pos[i]) == 1){
      c[i] = a[pos[i][0] + 1];
      continue;
    }else{
      if(n == 16) assert(len(pos[i]) > 5);
    int b = 32 - __builtin_clz(len(pos[i]) - 1);
    int cur = -len(x);
    c[i] = cur - 1;
    for(int j = 0; j < len(pos[i]) - 1; j ++){
      int x = 1;
      for(int bit = 0; bit < b; bit ++){
        if(j >> bit & 1){
          if(bit < b - 1){
            addy(cur - x, cur - (x * 2 + 1));
          }else{
            addy(cur - x, a[pos[i][j] + 1]);
          }
          x = x * 2 + 1;
        }else{
          if(bit < b - 1)
            addx(cur - x, cur - x * 2);
          else
            addx(cur - x, a[pos[i][j] + 1]);
          x *= 2;
        }
      }
    }
    for(int j = len(pos[i]) - 1; j < (1 << b) - 1; j ++){
      int x = 1;
      for(int bit = 0; bit < b; bit ++){
        if(j >> bit & 1){
          if(bit < b - 1){
            addy(cur - x, cur - (x * 2 + 1));
          }else{
            addy(cur - x, cur - 1);
          }
          x = x * 2 + 1;
        }else{
          if(bit < b - 1){
            addx(cur - x, cur - x * 2);
          }else
            addx(cur - x, cur - 1);
          x = x * 2;
        }
      }
    }
    int x = 1;
    for(int bit = 0; bit < b; bit ++){
      if(bit < b - 1){
        addy(cur - x, cur - (x * 2 + 1));
      }else addy(cur - x, a[pos[i].back() + 1]);
      x = x * 2 + 1;
    }
    }
  }

  answer(c, x, y);
 
}

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