Submission #220986

#	Time	Username	Problem	Language	Result	Execution time	Memory
220986		rama_pang	Library (JOI18_library)	C++14	100 / 100	352 ms	1204 KiB

library

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

int N;
vector<deque<int>> Deques; // set of Deques

int QueryDeque(int L, int R, int X, int exclude = -1) { // Query Deques[L...R] excluding exclude and element X
  vector<int> M(N);
  for (int Di = L; Di <= R; Di++) {
    if (Di == exclude) continue;
    for (auto i : Deques[Di]) {
      M[i] = 1;
    }
  }
  M[X] = 1;
  return Query(M);
}

int QueryElement(int A, int B) {
  vector<int> M(N);
  M[A] = M[B] = 1;
  return Query(M);
}

int ActiveDeque(int L, int R, int exclude = -1) {
  int res = 0;
  for (int Di = L; Di <= R; Di++) {
    if (Di == exclude) continue;
    if (Deques[Di].empty()) continue;
    res++;
  }
  return res;
}

int BinarySearch(int X, int exclude = -1) { // binary search for a D[] that is adjacent to X, excluding exlcude
  int lo = 0, hi = N - 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (QueryDeque(0, mid, X, exclude) <= ActiveDeque(0, mid, exclude)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return hi;
}

void Merge(int D1, int X) {
  bool IsFront = QueryElement(Deques[D1].front(), X) == 1;
  if (IsFront) {
    Deques[D1].emplace_front(X);
  } else {
    Deques[D1].emplace_back(X);
  }
}

void Merge(int D1, int D2, int X) {
  bool IsFrontD1 = QueryElement(Deques[D1].front(), X) == 1;
  bool IsFrontD2 = QueryElement(Deques[D2].front(), X) == 1;

  if (!IsFrontD1) reverse(begin(Deques[D1]), end(Deques[D1]));
  if (!IsFrontD2) reverse(begin(Deques[D2]), end(Deques[D2]));
  
  Deques[D2].emplace_front(X);
  while (!Deques[D1].empty()) {
    Deques[D2].emplace_front(Deques[D1].front());
    Deques[D1].pop_front();
  }
}

void Solve(int N) {
  ::N = N;
  Deques.resize(N);

  for (int X = 0; X < N; X++) {
    int DSize = ActiveDeque(0, N - 1);
    int AddX = QueryDeque(0, N - 1, X);
    if (AddX == DSize + 1) { // Add a new D[]
      Deques[X].emplace_back(X);
    } else if (AddX == DSize) { // Adjacent to an existing D[]
      int D1 = BinarySearch(X);
      Merge(D1, X);
    } else if (AddX == DSize - 1) { // Adjacent to 2 exsiting D[]
      int D1 = BinarySearch(X);
      int D2 = BinarySearch(X, D1);
      Merge(D1, D2, X);
    }
  }

  vector<int> res;
  for (auto &D : Deques) {
    for (auto i : D) {
      res.emplace_back(i + 1);
    }
  }

  return Answer(res);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81