oj.uz

Submission #1080591

# Submission time Handle Problem Language Result Execution time Memory
1080591 2024-08-29T11:28:23 Z shmax Longest Trip (IOI23_longesttrip) C++17
5 / 100
 9 ms 600 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 8 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 9 ms 344 KB Output is correct
4 Correct 6 ms 600 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -