Submission #893302

#	Time	Username	Problem	Language	Result	Execution time	Memory
893302		MilosMilutinovic	Fun Tour (APIO20_fun)	C++14	100 / 100	175 ms	21192 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) * 2 >= n) {
      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();
  if (k < 1 || k > 3) {
    while (true) {

    }
  }
  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 && mx > 0;
  };
  int lst = -1;
  vector<int> res;
  vector<int> group;
  while (Good()) {
    int who = -1;
    for (int i = 0; i < k; i++) {
      if (i == lst || ids[i].empty()) {
        continue;
      }
      if (who == -1 || dist[ids[who].back()] < dist[ids[i].back()]) {
        who = i;
      }
    }
    group.push_back(who);
    res.push_back(ids[who].back());
    ids[who].pop_back();
    lst = who;
  }
  int big = 0;
  for (int i = 0; i < k; i++) {
    if (ids[i].size() > ids[big].size()) {
      big = i;
    }
  }
  if ((int) group.size() >= 2 && !ids[group.rbegin()[1]].empty() && 
      dist[ids[group.rbegin()[1]].back()] > dist[ids[big].back()]) {
    res.push_back(ids[group.rbegin()[1]].back());
    ids[group.rbegin()[1]].pop_back();
  }
  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: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 34 / 34