Submission #1244766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244766		lncreedible	Mechanical Doll (IOI18_doll)	C++20	6 / 100	163 ms	16684 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> C;
vector<int> X;
vector<int> Y;
int swidc = 0;

int new_switch() {
    X.push_back(0);
    Y.push_back(0);
    return -(++swidc);
}

int br(size_t sid, size_t count, int killd, const vector<int>& dests) {
    if (count == 1) {
        if (sid < dests.size()) {
            return dests[sid];
        } else {
            return killd;
        }
    }
    
    int cursw = new_switch();
    size_t half = count / 2;
    
    int lc = br(sid, half, killd, dests);
    int rc = br(sid + half, half, killd, dests);
    
    X[-cursw - 1] = lc;
    Y[-cursw - 1] = rc;
    
    return cursw;
}
int cs(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 rtsw = new_switch();
    
    size_t half = m / 2;
    int lc = br(0, half, rtsw, dests);
    int rc = br(half, half, rtsw, dests);
    
    X[-rtsw - 1] = lc;
    Y[-rtsw - 1] = rc;
    
    return rtsw;
}

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

  if (N == 0) {
      answer(C, X, Y);
      return;
  }

  map<int, vector<int>> occs;
  for (int i = 0; i < N; ++i) {
      occs[A[i]].push_back(i);
  }

  C[0] = A[0];

  for (int t = 1; t <= M; ++t) {
      if (occs.find(t) == occs.end()) {
          C[t] = 0; 
          continue;
      }
      
      const auto& pos = occs.at(t);
      vector<int> des;
      des.reserve(pos.size());
      for (int pos : pos) {
          des.push_back((pos == N - 1) ? 0 : A[pos + 1]);
      }
      C[t] = cs(des);
  }
  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