Submission #1060252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060252		MilosMilutinovic	Park (JOI17_park)	C++14	67 / 100	235 ms	864 KiB

park

#include "park.h"
#include <bits/stdc++.h>

using namespace std;

static int Place[1400];

void Detect(int T, int n) {
  vector<bool> done(n);
  done[0] = true;
  vector<vector<int>> g(n);
  function<void(int)> Solve = [&](int v) {
    if (done[v]) {
      return;
    }
    while (true) {
      for (int i = 0; i < n; i++) {
        Place[i] = done[i] ? 1 : 0;
      }
      Place[v] = 1;
      if (Ask(0, v, Place)) {
        break;
      }
      int low = 0, high = n - 1, p = -1;
      while (low <= high) {
        int mid = (low + high) >> 1;
        for (int i = 0; i < n; i++) {
          if (done[i] || i == v || i <= mid) {
            Place[i] = 1;
          } else {
            Place[i] = 0;
          }
        }
        if (Ask(0, v, Place)) {
          p = mid;
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      Solve(p);
    }
    vector<int> que(1, 0);
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : g[i]) {
        que.push_back(j);
      }
    }
    int low = 0, high = (int) que.size() - 1, p = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      for (int i = 0; i < n; i++) {
        Place[i] = 0;
      }
      for (int i = 0; i <= mid; i++) {
        Place[que[i]] = 1;
      }
      Place[v] = 1;
      if (Ask(0, v, Place)) {
        p = que[mid];
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    g[p].push_back(v);
    Answer(min(p, v), max(p, v));
    done[v] = true;
  };
  for (int i = 1; i < n; i++) {
    if (!done[i]) {
      Solve(i);
    }
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23