oj.uz

Submission #220986

# Submission time Handle Problem Language Result Execution time Memory
220986 2020-04-09T11:30:17 Z rama_pang Library (JOI18_library) C++14
100 / 100
 352 ms 1204 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 512 KB # of queries: 1861
2 Correct 35 ms 512 KB # of queries: 1819
3 Correct 34 ms 512 KB # of queries: 1944
4 Correct 36 ms 512 KB # of queries: 1923
5 Correct 32 ms 512 KB # of queries: 1929
6 Correct 35 ms 512 KB # of queries: 1940
7 Correct 39 ms 512 KB # of queries: 1940
8 Correct 34 ms 512 KB # of queries: 1846
9 Correct 37 ms 512 KB # of queries: 1934
10 Correct 22 ms 384 KB # of queries: 1156
11 Correct 5 ms 384 KB # of queries: 1
12 Correct 4 ms 256 KB # of queries: 4
13 Correct 5 ms 256 KB # of queries: 9
14 Correct 5 ms 384 KB # of queries: 13
15 Correct 6 ms 256 KB # of queries: 85
16 Correct 7 ms 384 KB # of queries: 183

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 512 KB # of queries: 1861
2 Correct 35 ms 512 KB # of queries: 1819
3 Correct 34 ms 512 KB # of queries: 1944
4 Correct 36 ms 512 KB # of queries: 1923
5 Correct 32 ms 512 KB # of queries: 1929
6 Correct 35 ms 512 KB # of queries: 1940
7 Correct 39 ms 512 KB # of queries: 1940
8 Correct 34 ms 512 KB # of queries: 1846
9 Correct 37 ms 512 KB # of queries: 1934
10 Correct 22 ms 384 KB # of queries: 1156
11 Correct 5 ms 384 KB # of queries: 1
12 Correct 4 ms 256 KB # of queries: 4
13 Correct 5 ms 256 KB # of queries: 9
14 Correct 5 ms 384 KB # of queries: 13
15 Correct 6 ms 256 KB # of queries: 85
16 Correct 7 ms 384 KB # of queries: 183
17 Correct 352 ms 1048 KB # of queries: 11961
18 Correct 345 ms 1144 KB # of queries: 11824
19 Correct 346 ms 1204 KB # of queries: 11981
20 Correct 317 ms 1020 KB # of queries: 11222
21 Correct 288 ms 1144 KB # of queries: 10600
22 Correct 351 ms 1144 KB # of queries: 11963
23 Correct 350 ms 1024 KB # of queries: 11948
24 Correct 118 ms 768 KB # of queries: 5636
25 Correct 333 ms 1144 KB # of queries: 11697
26 Correct 296 ms 1024 KB # of queries: 10977
27 Correct 114 ms 640 KB # of queries: 5611
28 Correct 317 ms 1144 KB # of queries: 11989
29 Correct 320 ms 1084 KB # of queries: 11977
30 Correct 341 ms 1048 KB # of queries: 11989