oj.uz

Submission #1080608

# Submission time Handle Problem Language Result Execution time Memory
1080608 2024-08-29T11:36:03 Z shmax Longest Trip (IOI23_longesttrip) C++17
15 / 100
 8 ms 596 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[0];
            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[1];
                    ans.push_back(net);
                    not_used.erase(net);
                    cur = net;
                }
            }
        }
        return vec<int>(all(ans));
    }
}

Compilation message

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

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 3 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
10.0 / 10.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 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 7 ms 344 KB Output is correct
11 Correct 7 ms 480 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 7 ms 596 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 6 ms 464 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 8 ms 344 KB Output is correct
13 Correct 7 ms 460 KB Output is correct
14 Incorrect 0 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 8 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 7 ms 344 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 7 ms 344 KB Output is correct
14 Incorrect 0 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -