Submission #1080591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080591		shmax	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	9 ms	600 KiB

longesttrip

#include "longesttrip.h"
#include "bits/stdc++.h"

using namespace std;
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define inf 1000'000'000'000'000'000LL
#define bit(x, i) (((x) >> i) & 1)


template<typename T>
using vec = vector<T>;

std::vector<int> longest_trip(int n, int d) {
    mt19937 rnd(14345);
    if (d == 3) {
        vec<int> ans(n);
        iota(all(ans), 0);
        return ans;
    }
    if (d == 2) {
        deque<int> ans;
        int cur = 0;
        ans.push_back(cur);
        set<int> not_used;
        for (int i = 1; i < n; i++) {
            not_used.insert(i);
        }
        while (true) {
            if(not_used.empty()) break;
            vec<int> next(all(not_used));
            int nxt = next[rnd() % len(next)];
            if (are_connected({cur}, {nxt})) {
                ans.push_back(nxt);
                not_used.erase(nxt);
                cur = nxt;
            } else {
                if (next.size() == 1) {
                    ans.push_front(next[0]);
                    break;
                } else {
                    int net = next[rnd() % len(next)];
                    while (net == nxt) {
                        net = next[rnd() % len(next)];
                    }
                    ans.push_back(net);
                    not_used.erase(net);
                }
            }
        }
        return vec<int>(all(ans));
    }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60