Submission #446820

#	Time	Username	Problem	Language	Result	Execution time	Memory
446820		cs71107	자동 인형 (IOI18_doll)	C++14	100 / 100	111 ms	14392 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+10;

int tree[MAXN*4];
int cal[MAXN*4];
int id[MAXN*4];

void create_circuit(int M, std::vector<int> A) {
  
  int n = (int)A.size();

  vector<int> C;
  vector<int> X;
  vector<int> Y;

  C = vector<int> (M+1);

  if(n==1){

    C[0] = A[0];
    
    answer(C,X,Y);

    return;
  }

  int base = 1;

  for(;base<n;base<<=1);

  for(int i=base-1;i>=base-n;i--){
    tree[i+base] = 1;
  }

  for(int i=base-1;i>=1;i--){
    tree[i] = tree[(i<<1)]|tree[(i<<1)|1];
  }

  vector<int> ord;

  int cur = 1;

  for(int i=0;i<base;i++){

    cur = 1;

    while(cur<base){
      if(cal[cur]){
        cal[cur] = 0;
        cur<<=1;
        cur|=1;
      }
      else {
        cal[cur] = 1;
        cur<<=1;
      }
    }

    if(tree[cur]){
      ord.push_back(cur-base);
    }
  }

  assert((int)ord.size()==n);

  int cnt = 0;

  for(int i=1;i<base;i++){
    if(tree[i]){
      cnt++;
      id[i] = -cnt;
    }
  }

  for(int i=0;i<n;i++){
    if(i==n-1)id[ord[i]+base] = 0;
    else id[ord[i]+base] = A[i+1];
  }

  C[0] = A[0];

  for(int i=1;i<=M;i++){
    C[i] = -1;
  }

  X = vector<int> (cnt);
  Y = vector<int> (cnt);

  int cidx = 0;

  for(int i=1;i<base;i++){
    if(tree[i]){
      
      if(tree[(i<<1)]){
        X[cidx] = id[(i<<1)];
      }
      else {
        X[cidx] = -1;
      }

      if(tree[(i<<1)|1]){
        Y[cidx] = id[(i<<1)|1];
      }
      else {
        Y[cidx] = -1;
      }

      cidx++;
    }
  }

  answer(C,X,Y);

  return;
}

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