Submission #293418

#	Time	Username	Problem	Language	Result	Execution time	Memory
293418		rama_pang	Fun Tour (APIO20_fun)	C++14	100 / 100	371 ms	20376 KiB

fun

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

vector<int> createFunTour(int N, int Q) {
  auto Centroid = [&]() {
    int val = -1, res = -1;
    for (int i = 0; i < N; i++) {
      int q = attractionsBehind(0, i);
      if ((N - q) * 2 <= N) {
        if (val <= N - q) {
          val = N - q;
          res = i;
        }
      }
    }
    assert(res != -1);
    return res;
  };

  int u = Centroid();
  vector<int> other;
  vector<int> dist(N);
  for (int i = 0; i < N; i++) {
    dist[i] = hoursRequired(u, i);
    if (i != u) {
      other.emplace_back(i);
    }
  }
  sort(begin(other), end(other), [&](int i, int j) {
    return dist[i] < dist[j];
  });
  int zero = 0;
  while (zero + 1 < N && dist[other[zero]] == 1) {
    zero++;
  }
  assert(zero <= 3);
  vector<vector<int>> sub(zero);
  for (int i = 0; i < zero; i++) {
    sub[i].emplace_back(other[i]);
    assert(attractionsBehind(u, other[i]) * 2 <= N);
  }
  for (int i = zero; i + 1 < N; i++) {
    int v = other[i];
    bool inserted = false;
    for (int z = 0; z + 1 < zero; z++) {
      if (!inserted && 1 + hoursRequired(sub[z][0], v) == dist[v]) {
        assert(!inserted);
        inserted = true;
        sub[z].emplace_back(v);
      }
    }
    if (!inserted) {
      sub.back().emplace_back(v);
    }
  }

  int last = -1;
  vector<int> res;
  while (res.size() < N) {
    array<int, 3> mx = {-1, -1, -1}; // (dist, size, id)
    int total = 0;
    for (int i = 0; i < (int) sub.size(); i++) {
      total += sub[i].size();
    }
    static int big = -1;
    for (int i = 0; i < (int) sub.size(); i++) {
      if (big == -1 && 2 * sub[i].size() >= total) {
        int allmx = -1;
        for (int j = 0; j < (int) sub.size(); j++) {
          if (!sub[j].empty()) {
            allmx = max(allmx, dist[sub[j].back()]);
          }
        }
        if (last == -1 || sub[i].empty() || dist[sub[last].back()] == allmx || dist[sub[i].back()] == allmx) {
          big = i;
        }
      }
    }
    for (int i = 0; i < (int) sub.size(); i++) {
      if (i != last && !sub[i].empty()) {
        mx = max(mx, {dist[sub[i].back()], (int) sub[i].size(), i});
      }
    }
    if (big != -1 && last != big) {
      if (sub[big].empty()) {
        mx[2] = -1;
      } else {
        mx[2] = big;
      }
    }
    if (mx[2] == -1) {
      res.emplace_back(u);
    } else {
      res.emplace_back(sub[mx[2]].back());
      sub[mx[2]].pop_back();
    }
    last = mx[2];
  }

  return res;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:60:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |   while (res.size() < N) {
      |          ~~~~~~~~~~~^~~
fun.cpp:68:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |       if (big == -1 && 2 * sub[i].size() >= total) {
      |                        ~~~~~~~~~~~~~~~~~~^~~~~~~~

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