Submission #726847

#	Time	Username	Problem	Language	Result	Execution time	Memory
726847		LittleFlowers__	Fun Tour (APIO20_fun)	C++17	26 / 100	243 ms	524288 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

mt19937 rng(101202);
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) {
  if (l > r) { cerr << l << " " << r << "\n"; }
  return l + rng() % (r - l + 1);
}

vector<int> createFunTour(int n, int q) {
  vector<vector<int>> distance(n, vector<int>(n));
  vector<pair<int, int>> edges;
  vector<bool> visited(n);
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
    distance[i][j] = distance[j][i] = hoursRequired(i, j);
    edges.push_back({i, j});
    edges.push_back({j, i});
  }

  sort(edges.begin(), edges.end(), [&](pair<int, int> x, pair<int, int> y) {
    return distance[x.first][x.second] > distance[y.first][y.second];
  });

  int currentVertex = edges[0].first, fun = n;
  visited[currentVertex] = true;
  vector<int> answer = {currentVertex};
  for (int i = 1; i < n; ++i) {
    bool found = false;
    for (const auto [x, y] : edges) {
      if (x != currentVertex || !visited[x] || visited[x] && visited[y] || fun < distance[x][y]) continue;
      answer.push_back(currentVertex = y);
      visited[y] = true;
      found = true;
      break;
    }
    assert(found);
  }

  return answer;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:80:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |       if (x != currentVertex || !visited[x] || visited[x] && visited[y] || fun < distance[x][y]) continue;
      |                                                ~~~~~~~~~~~^~~~~~~~~~~~~

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