oj.uz

Submission #1033192

# Submission time Handle Problem Language Result Execution time Memory
1033192 2024-07-24T14:03:54 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
100 / 100
 13 ms 600 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
bool check (int x, int y) {
    assert(x != y);
    return are_connected({x}, {y});
}
vector <int> longest_trip (int n, int d) {
    vector <int> x, y;  
    x.push_back(0);  
    y.push_back(1);
    for (int i = 2; i + 1 < n; i += 2) {
        int u = i, v = i + 1;
        if (check(u, v)) {
            if (check(u, x.back())) {
                x.push_back(u); x.push_back(v);
            } else if (check(u, y.back())) {
                y.push_back(u); y.push_back(v);
            } else {
                reverse(y.begin(), y.end());
                for (auto j : y) {
                    x.push_back(j);
                }
                y.clear();
                y.push_back(u); y.push_back(v);
            }
        } else { //preferably make a flowchart for this part
            if (check(u, x.back())) {
                x.push_back(u);
                if (check(v, y.back())) {
                    y.push_back(v);
                } else {
                    reverse(y.begin(), y.end());
                    for (auto j : y) {
                        x.push_back(j);
                    }
                    y.clear();
                    y.push_back(v);
                }
            } else {
                x.push_back(v);
                if (check(u, y.back())) {
                    y.push_back(u);
                } else {
                    reverse(y.begin(), y.end());
                    for (auto j : y) {
                        x.push_back(j);
                    }
                    y.clear();
                    y.push_back(u);
                }
            }
        }
    }
    if (n & 1) {
        int i = n - 1;
        bool f = check(x.back(), i);
        bool g = check(y.back(), i);
        if (!f && !g) {
            reverse(y.begin(), y.end());
            for (auto j : y) {
                x.push_back(j);
            }
            y.clear();
            y.push_back(i);
        } else if (f) {
            x.push_back(i);
        } else {
            y.push_back(i);
        }
    }
    if (!are_connected(x, y)) {
        if (x.size() < y.size()) {
            swap(x, y);
        }
        return x;
    }
    vector <int> gg = {x.front()}, hh = {y.front()};
    if (x.size() != 1) gg.push_back(x.back());
    if (y.size() != 1) hh.push_back(y.back());
    for (auto i : gg) {
        for (auto j : hh) {
            if (are_connected({i}, {j})) {
                if (i == x.front()) {
                    reverse(x.begin(), x.end());
                }
                if (j == y.back()) {
                    reverse(y.begin(), y.end());
                }
                for (auto g : y) {
                    x.push_back(g);
                }
                return x;
            }
        }
    } 
    int L1 = 0, R1 = int(x.size()) - 1, ANS1 = -1;
    while (L1 <= R1) {
        int mid = (L1 + R1) / 2;
        vector <int> dd;
        for (int i = 0; i <= mid; i++) {
            dd.push_back(x[i]);
        }
        if (are_connected(dd, y)) {
            R1 = mid - 1; ANS1 = mid;
        } else {
            L1 = mid + 1;
        }
    }
    for (int i = ANS1; i <= ANS1; i++) {
        int l = 0, r = int(y.size()) - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            vector <int> dd;
            for (int j = 0; j <= mid; j++) {
                dd.push_back(y[j]);
            }
            if (are_connected({x[i]}, dd)) {
                r = mid - 1; ans = mid;
            } else {
                l = mid + 1;
            }
        }
        if (ans == -1) continue;
        vector <int> ret;
        for (int j = i - 1; j >= 0; j--) {
            ret.push_back(x[j]);
        }
        for (int j = int(x.size()) - 1; j > i; j--) {
            ret.push_back(x[j]);
        }
        ret.push_back(x[i]);
        ret.push_back(y[ans]);
        for (int j = ans + 1; j < int(y.size()); j++) {
            ret.push_back(y[j]);
        }
        for (int j = 0; j < ans; j++) {
            ret.push_back(y[j]);
        }
        return ret;
    }
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:10:18: warning: control reaches end of non-void function [-Wreturn-type]
   10 |     vector <int> x, y;
      |                  ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 2 ms 344 KB Output is correct

Subtask #1
5.0 / 5.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 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 9 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 432 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 8 ms 356 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 10 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 6 ms 344 KB Output is correct
20 Correct 4 ms 344 KB Output is correct
21 Correct 6 ms 444 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 6 ms 436 KB Output is correct
24 Correct 8 ms 436 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 8 ms 344 KB Output is correct
27 Correct 8 ms 344 KB Output is correct
28 Correct 6 ms 344 KB Output is correct
29 Correct 8 ms 344 KB Output is correct
30 Correct 5 ms 340 KB Output is correct
31 Correct 8 ms 344 KB Output is correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 6 ms 344 KB Output is correct
34 Correct 4 ms 344 KB Output is correct
35 Correct 5 ms 344 KB Output is correct
36 Correct 5 ms 344 KB Output is correct
37 Correct 3 ms 344 KB Output is correct
38 Correct 7 ms 344 KB Output is correct
39 Correct 8 ms 340 KB Output is correct
40 Correct 5 ms 344 KB Output is correct
41 Correct 9 ms 344 KB Output is correct
42 Correct 7 ms 344 KB Output is correct
43 Correct 10 ms 344 KB Output is correct
44 Correct 5 ms 344 KB Output is correct
45 Correct 7 ms 344 KB Output is correct
46 Correct 6 ms 344 KB Output is correct
47 Correct 8 ms 344 KB Output is correct
48 Correct 10 ms 344 KB Output is correct
49 Correct 8 ms 344 KB Output is correct
50 Correct 4 ms 436 KB Output is correct
51 Correct 9 ms 344 KB Output is correct
52 Correct 7 ms 344 KB Output is correct
53 Correct 6 ms 344 KB Output is correct
54 Correct 6 ms 344 KB Output is correct
55 Correct 6 ms 344 KB Output is correct
56 Correct 6 ms 436 KB Output is correct
57 Correct 5 ms 344 KB Output is correct
58 Correct 7 ms 344 KB Output is correct
59 Correct 7 ms 344 KB Output is correct
60 Correct 7 ms 344 KB Output is correct
61 Correct 7 ms 344 KB Output is correct
62 Correct 8 ms 440 KB Output is correct
63 Correct 10 ms 344 KB Output is correct
64 Correct 8 ms 440 KB Output is correct

Subtask #4
60.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 8 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 6 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 5 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 7 ms 600 KB Output is correct
19 Correct 6 ms 344 KB Output is correct
20 Correct 6 ms 344 KB Output is correct
21 Correct 4 ms 344 KB Output is correct
22 Correct 6 ms 344 KB Output is correct
23 Correct 6 ms 344 KB Output is correct
24 Correct 6 ms 344 KB Output is correct
25 Correct 9 ms 344 KB Output is correct
26 Correct 5 ms 424 KB Output is correct
27 Correct 6 ms 344 KB Output is correct
28 Correct 7 ms 344 KB Output is correct
29 Correct 9 ms 344 KB Output is correct
30 Correct 5 ms 344 KB Output is correct
31 Correct 4 ms 344 KB Output is correct
32 Correct 8 ms 344 KB Output is correct
33 Correct 10 ms 344 KB Output is correct
34 Correct 7 ms 344 KB Output is correct
35 Correct 9 ms 344 KB Output is correct
36 Correct 11 ms 344 KB Output is correct
37 Correct 8 ms 344 KB Output is correct
38 Correct 8 ms 436 KB Output is correct
39 Correct 8 ms 344 KB Output is correct
40 Correct 9 ms 344 KB Output is correct
41 Correct 6 ms 344 KB Output is correct
42 Correct 6 ms 344 KB Output is correct
43 Correct 6 ms 344 KB Output is correct
44 Correct 8 ms 344 KB Output is correct
45 Correct 6 ms 344 KB Output is correct
46 Correct 4 ms 340 KB Output is correct
47 Correct 5 ms 344 KB Output is correct
48 Correct 4 ms 344 KB Output is correct
49 Correct 4 ms 344 KB Output is correct
50 Correct 6 ms 344 KB Output is correct
51 Correct 7 ms 344 KB Output is correct
52 Correct 5 ms 344 KB Output is correct
53 Correct 10 ms 344 KB Output is correct
54 Correct 6 ms 344 KB Output is correct
55 Correct 6 ms 340 KB Output is correct
56 Correct 5 ms 344 KB Output is correct
57 Correct 4 ms 344 KB Output is correct
58 Correct 5 ms 344 KB Output is correct
59 Correct 7 ms 344 KB Output is correct
60 Correct 7 ms 344 KB Output is correct
61 Correct 7 ms 344 KB Output is correct
62 Correct 6 ms 344 KB Output is correct
63 Correct 9 ms 344 KB Output is correct
64 Correct 7 ms 440 KB Output is correct
65 Correct 7 ms 340 KB Output is correct
66 Correct 8 ms 344 KB Output is correct
67 Correct 6 ms 344 KB Output is correct
68 Correct 9 ms 600 KB Output is correct
69 Correct 7 ms 600 KB Output is correct
70 Correct 8 ms 600 KB Output is correct
71 Correct 6 ms 344 KB Output is correct
72 Correct 7 ms 440 KB Output is correct
73 Correct 6 ms 344 KB Output is correct
74 Correct 8 ms 436 KB Output is correct
75 Correct 11 ms 344 KB Output is correct
76 Correct 7 ms 344 KB Output is correct
77 Correct 6 ms 440 KB Output is correct
78 Correct 5 ms 344 KB Output is correct
79 Correct 7 ms 344 KB Output is correct
80 Correct 10 ms 444 KB Output is correct
81 Correct 7 ms 344 KB Output is correct
82 Correct 8 ms 344 KB Output is correct