제출 #1244786

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

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> C;
vector<int> X;
vector<int> Y;
int switch_counter = 0;

int nsw() {
    X.push_back(0);
    Y.push_back(0);
    return -(++switch_counter);
}


int br(size_t start_idx, size_t count, int kill_dest, const vector<int>& dests) {
    if (count == 1) {
        if (start_idx < dests.size()) {
            return dests[start_idx];
        }
        else {
            return kill_dest;
        }
    }
    
    int csw = nsw();
    size_t half = count / 2;
    
    int lc = br(start_idx, half, kill_dest, dests);
    int rc = br(start_idx + half, half, kill_dest, dests);
    
    X[-csw - 1] = lc;
    Y[-csw - 1] = rc;
    
    return csw;
}

int cms(const vector<int>& dests) {
    size_t k = dests.size();
    if (k == 0) return 0;
    if (k == 1) return dests[0];

    size_t m = 1;
    while (m < k) {
        m *= 2;
    }

    int rsw = nsw();
    
    size_t half = m / 2;
    int lc = br(0, half, rsw, dests);
    int rc = br(half, half, rsw, dests);
    
    X[-rsw - 1] = lc;
    Y[-rsw - 1] = rc;
    
    return rsw;
}

void create_circuit(int M, vector<int> A) {
  int N = A.size();
  C.assign(M + 1, 0);

  vector<int> destinations = A;
  destinations.push_back(0); 

  size_t k = destinations.size();
  if (k == 1) { 
      answer(C, X, Y);
      return;
  }

  int master_root = cms(destinations);

  C[0] = master_root;
  
  vector<bool> is_trigger_used(M + 1, false);
  for (int trigger_id : A) {
      if (trigger_id > 0 && trigger_id <= M) {
          is_trigger_used[trigger_id] = true;
      }
  }

  for (int t = 1; t <= M; ++t) {
      if (is_trigger_used[t]) {
          C[t] = master_root;
      }
  }
  
  answer(C, X, Y);
}

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