Submission #893286

#	Time	Username	Problem	Language	Result	Execution time	Memory
893286		MilosMilutinovic	Fun Tour (APIO20_fun)	C++14	0 / 100	800 ms	524288 KiB

fun

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

using namespace std;

vector<int> createFunTour(int n, int q) {
  auto AskDist = [&](int x, int y) {
    return hoursRequired(x, y);
  };
  auto AskSize = [&](int x, int y) {
    return attractionsBehind(x, y);
  };
  int cen = 0;
  for (int i = 1; i < n; i++) {
    if (AskSize(cen, i) >= n / 2) {
      cen = i;
    }
  }
  vector<int> dist(n);
  for (int i = 0; i < n; i++) {
    if (i == cen) {
      continue;
    }
    dist[i] = AskDist(cen, i);
  }
  vector<int> ch;
  for (int i = 0; i < n; i++) {
    if (dist[i] == 1) {
      ch.push_back(i);
    }
  }
  int k = (int) ch.size();
  vector<vector<int>> ids(k);
  for (int i = 0; i < n; i++) {
    if (i == cen) {
      continue;
    }
    int p = k - 1;
    for (int j = 0; j + 1 < k; j++) {
      if (AskDist(ch[j], i) == dist[i] - dist[ch[j]]) {
        p = j;
      }
    }
    ids[p].push_back(i);
  }
  for (int i = 0; i < k; i++) {
    sort(ids[i].begin(), ids[i].end(), [&](int i, int j) {
      return dist[i] < dist[j];
    });
  }
  auto Good = [&]() {
    int mx = 0, cnt = 0;
    for (int i = 0; i < k; i++) {
      mx = max(mx, (int) ids[i].size());
      cnt += (int) ids[i].size();
    }
    return mx < cnt - mx;
  };
  int lst = -1;
  vector<int> res;
  while (Good()) {
    int who = -1;
    for (int i = 0; i < k; i++) {
      if (i == lst) {
        continue;
      }
      if (who == -1 || dist[ids[who].back()] < dist[ids[i].back()]) {
        who = i;
      }
    }
    res.push_back(ids[who].back());
    lst = who;
  }
  int big = 0;
  for (int i = 0; i < k; i++) {
    if (ids[i].size() > ids[big].size()) {
      big = i;
    }
  }
  while (!ids[big].empty()) {
    res.push_back(ids[big].back());
    ids[big].pop_back();
    int who = -1;
    for (int i = 0; i < k; i++) {
      if (i == big || ids[i].empty()) {
        continue;
      }
      if (who == -1 || dist[ids[who].back()] < dist[ids[i].back()]) {
        who = i;
      }
    }
    if (who != -1) {
      res.push_back(ids[who].back());
      ids[who].pop_back();
    }
  }
  res.push_back(cen);
  return res;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34