Submission #726759

#	Time	Username	Problem	Language	Result	Execution time	Memory
726759		LittleFlowers__	Fun Tour (APIO20_fun)	C++17	0 / 100	7 ms	440 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

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));
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
    distance[i][j] = distance[j][i] = hoursRequired(i, j);
  }

  vector<int> state(n); iota(state.begin(), state.end(), 0);

  function<int(const vector<int>&)> evaluate = [&](const vector<int> &state) {
    int fault = 0;
    for (int i = 2; i < state.size(); ++i) {
      fault +=
        distance[state[i - 2]][state[i - 1]] < distance[state[i - 1]][state[i]];
    }
    return fault;
  };

  int temperature = 1e7;
  int best = evaluate(state);
  while (best) {
    int x = rnd(0, n - 1);
    int y = rnd(0, n - 1);
    if (x == y) continue;
    swap(state[x], state[y]);
    int adjValue = evaluate(state);
    if (
      adjValue < best
        || exp((best - adjValue) / temperature > rng() / (double)rng.max())
    ) best = adjValue;
    else                  swap(state[x], state[y]);
    temperature *= 0.9999;
  }

  return state;  
}

Compilation message (stderr)

fun.cpp: In lambda function:
fun.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 2; i < state.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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