제출 #1309146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309146		nikaa123	자동 인형 (IOI18_doll)	C++20	100 / 100	68 ms	15124 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define deb(x)  cout << #x << " ---> " << x << endl
using namespace std;

// void answer(vector <int> C, vector <int> X, vector <int> Y) {
//     cout << C.size() << endl;
//     for (auto x:C) {
//         cout << x << " " ;
//     }
//     cout << endl;
//     cout << X.size() << endl;
//     for (int i = 0; i < X.size(); i++) {
//         cout << X[i] << " " << Y[i] << endl;
//     }
// }

int arr[2000005];
int fix[2000005];
int id[2000005];


int rev(int x, int k) {
  int res = 0;
  for (int i = 0; i < k; i++) {
    if (x&(1<<i)) res += (1<<(k-1-i));
  }
  return res;
}

void create_circuit(int M, vector<int> A) {

  A.push_back(0);
  int N = A.size();
  // deb(N);
  vector<int> C(M + 1);
  for (int i = 0; i <= M; ++i) {
    C[i] = -1;
  }
  vector<int> X, Y;

  int k = 0;
  while ((1<<k) < N) {
    k++;
  }
  int S = 2;
  int cur = 2;
  vector <int> res;
  res.push_back(1);
  X.push_back(-1);
  Y.push_back(-1);
  while (cur < N) {
    vector <int> nres;
    for (auto x:res) {
      X[x-1] = (0-S);
      Y[x-1] = (0-S-1);
      X.push_back(-1);
      Y.push_back(-1);
      X.push_back(-1);
      Y.push_back(-1);
      nres.push_back(S);
      nres.push_back(S+1);
      S += 2;
      cur += 2;
    }
    res = nres;
  }
  // answer(C,X,Y);
  // for (auto x:res) {
  //   cout << x << " ";
  // }
  // cout << endl;
  int xr = cur - N;
  for (int i = 0; i < xr; i++) {
    int ind = i;
    if (ind%2==0) {
      X[res[ind/2]-1] = -1;
    } else {
      Y[res[ind/2]-1] = -1;
    }
  }
  vector <pair<int,int>> lst;
  for (int i = xr; i < cur; i++) {
    lst.push_back({rev(i,k),i});
  }
  sort(lst.begin(),lst.end());
  for (int i = xr; i < cur; i++) {
    auto [val,ind] = lst[i-xr];
    // deb(ind);
    if (ind%2==0) {
      X[res[ind/2]-1] = A[i-xr];
    } else {
      Y[res[ind/2]-1] = A[i-xr];
    }
  }

  S--;
  int ns = S;
  for (int i = 1; i <= S; i++) {
    arr[i*2] = X[i-1];
    arr[i*2+1] = Y[i-1];
  }
  for (int i = 2*S+1; i >= 2; i -= 2) {
    if (arr[i] == -1 && arr[i-1] == -1) {
      arr[i] = arr[i-1] = INT_MAX;
      arr[i/2] = -1;
      X[i/2-1]=Y[i/2-1] = INT_MAX;
      ns--;
      fix[i/2] = 1;
      if ((i/2)%2==1) {
        Y[i/4-1] = -1;
      } else {
        X[i/4-1] = -1;
      }
    }
  }

  cur = 1;
  for (int i = 1; i <= S; i++) {
    if (fix[i]) continue;
    id[i] = cur++;
  }  
  vector <int> X1(ns),Y1(ns);
  for (int i = 1; i <= S; i++) {
    if (fix[i]) continue; 
    int vx = X[i-1];
    if (vx < 0) {
      vx = (0-id[abs(vx)]);
    }
    int vy = Y[i-1];
    if (vy < 0) {
      vy = (0-id[abs(vy)]);
    }
    int ni = id[i];
    X1[ni-1] = vx;
    Y1[ni-1] = vy;
  }

  answer(C, X1, Y1);
}

// int main () {

//     int n,m;
//     cin >> m;
//     cin >> n;
//     vector <int> a(n);
//     for (int i= 1; i <= n; i++) {
//         cin >> a[i-1];
//     }
//     create_circuit(m,a);


// }

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