Submission #560622

#	Time	Username	Problem	Language	Result	Execution time	Memory
560622		piOOE	Fun Tour (APIO20_fun)	C++17	26 / 100	245 ms	524288 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) begin(x), end(x)

vector<int> createFunTour(int n, int q) {
    const int infI = 1e9 + 7;
    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            dist[i][j] = dist[j][i] = hoursRequired(i, j);
        }
    }
    int j = 0;
    pair<int, int> mxx = {-infI, -infI};
    for (; j < n; ++j) {
        mxx = max(mxx, make_pair(dist[j][0], j));
    }
    j = mxx.second;
    vector<int> ans;
    vector<bool> used(n);
    int lst = infI;
    for (int k = 0; k < n; ++k) {
        ans.push_back(j);
        used[j] = true;
        pair<int, int> mx = {-infI, -infI};
        for (int z = 0; z < n; ++z) {
            if (!used[z] && dist[j][z] <= lst) {
                mx = max(mx, make_pair(dist[j][z], z));
            }
        }
        if (mx.first == -infI) {
            break;
        }
        lst = mx.first;
        j = mx.second;
    }
    if (ans.size() == n) {
        return ans;
    }
    assert(false);
    return {};
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     if (ans.size() == n) {
      |         ~~~~~~~~~~~^~~~

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