제출 #1244752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244752		2288	자동 인형 (IOI18_doll)	C++20	6 / 100	50 ms	11192 KiB

doll

#include "doll.h"

using namespace std;

#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;

int rev_bit(int x, int l){
  int y=0;
  for (int i=0;i<l;i++){
    y=y*2+x%2;
    x/=2;
  }
  return y;
}

int ind_to_x(int i){
  return -i-1;
}

int gen(vi& X, vi& Y, vi& dest){
  int n=1;while(n<dest.size())n*=2;
  int xi = X.size()-1;
  vi dest2(n,ind_to_x(xi+1));

  for (int i=0;i<dest.size()-1;i++)dest2[rev_bit(i,n)]=dest[i];
  dest2[n-1] = dest.back();

  for (int i=1;i<n/2;i++){
    X.pb(ind_to_x(xi+i*2));
    Y.pb(ind_to_x(xi+i*2+1));
  }

  for (int i=0;i<n;i+=2){
    X.pb(dest2[i]);
    Y.pb(dest2[i+1]);
  }
  return ind_to_x(xi+1);
}

void create_circuit(int m, std::vector<int> A) {
  int n = A.size();
  std::vector<int> C(m + 1);

  vvi dest(m+1,vi());
  for (int i=0;i<n-1;i++)dest[A[i]].pb(A[i+1]);
  dest[A[n-1]].pb(0);

  vi X,Y;

  for (int i=1;i<=m;i++){
    int ds=dest[i].size();
    if (ds==0){
      C[i]=0;
      continue;
    }
    if (ds==1){
      C[i] = dest[i][0];
      continue;
    }
    C[i]=gen(X,Y,dest[i]);
  }

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

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