oj.uz

Submission #876834

# Submission time Handle Problem Language Result Execution time Memory
876834 2023-11-22T12:09:58 Z MinaRagy06 Longest Trip (IOI23_longesttrip) C++17
85 / 100
 20 ms 884 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;

vector<int> longest_trip(int n, int d) {
    if (d == 3) {
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            ans.push_back(i);
        }
        return ans;
    } else if (d == 2) {
        vector<int> rem;
        for (int i = 1; i < n; i++) {
            rem.push_back(i);
        }
        vector<int> ans;
        ans.push_back(0);
        while (rem.size()) {
            if (are_connected({ans.back()}, {rem.back()})) {
                ans.push_back(rem.back());
                rem.pop_back();
            } else {
                int x = rem.back();
                rem.pop_back();
                if (rem.size()) {
                    ans.push_back(rem.back());
                    rem.pop_back();
                    rem.push_back(x);
                } else {
                    rem.push_back(x);
                    break;
                }
            }
        }
        if (rem.size()) {
            reverse(ans.begin(), ans.end());
            ans.push_back(rem.back());
        }
        return ans;
    } else {
        vector<int> v[2];
        v[0].push_back(0);
        for (int i = 1; i < n; i++) {
            if (are_connected({v[0].back()}, {i})) {
                v[0].push_back(i);
            } else if (v[1].size() && are_connected({v[1].back()}, {i})) {
                v[1].push_back(i);
            } else {
                reverse(v[1].begin(), v[1].end());
                for (auto j : v[1]) {
                    v[0].push_back(j);
                }
                v[1] = {i};
            }
        }
        if (v[1].empty()) return v[0];
        if (are_connected({v[1][0]}, {v[0][0]})) {
            reverse(v[0].begin(), v[0].end());
            for (auto i : v[1]) {
                v[0].push_back(i);
            }
            return v[0];
        } else if (are_connected({v[1][0]}, {v[0].back()})) {
            for (auto i : v[1]) {
                v[0].push_back(i);
            }
            return v[0];
        } else if (are_connected({v[1].back()}, {v[0][0]})) {
            for (auto i : v[0]) {
                v[1].push_back(i);
            }
            return v[1];
        } else if (are_connected({v[1].back()}, {v[0].back()})) {
            reverse(v[1].begin(), v[1].end());
            for (auto i : v[1]) {
                v[0].push_back(i);
            }
            return v[0];
        } else {
            int l = 0, r = v[0].size() - 1;
            while (l <= r) {
                int md = (l + r) >> 1;
                vector<int> cur;
                for (int k = l; k <= md; k++) {
                    cur.push_back(v[0][k]);
                }
                if (are_connected(cur, v[1])) {
                    r = md - 1;
                } else {
                    l = md + 1;
                }
            }
            int i = l;
            if (i == v[0].size()) {
                if (v[0].size() > v[1].size()) {
                    return v[0];
                } else {
                    return v[1];
                }
            }
            l = 0, r = v[1].size();
            while (l <= r) {
                int md = (l + r) >> 1;
                vector<int> cur;
                for (int k = l; k <= md; k++) {
                    cur.push_back(v[1][k]);
                }
                if (are_connected({v[0][i]}, cur)) {
                    r = md - 1;
                } else {
                    l = md + 1;
                }
            }
            int j = l;
            vector<int> x[2];
            for (int k = i + 1; k < v[0].size(); k++) {
                x[0].push_back(v[0][k]);
            }
            for (int k = 0; k <= i; k++) {
                x[0].push_back(v[0][k]);
            }
            for (int k = j + 1; k < v[1].size(); k++) {
                x[1].push_back(v[1][k]);
            }
            for (int k = 0; k <= j; k++) {
                x[1].push_back(v[1][k]);
            }
            reverse(x[1].begin(), x[1].end());
            vector<int> ans = x[0];
            for (auto k : x[1]) {
                ans.push_back(k);
            }
            return ans;
            /*for (int i = 0; i < v[0].size(); i++) {
                for (int j = 0; j < v[1].size(); j++) {
                    if (are_connected({v[0][i]}, {v[1][j]})) {
                        vector<int> x[2];
                        for (int k = i + 1; k < v[0].size(); k++) {
                            x[0].push_back(v[0][k]);
                        }
                        for (int k = 0; k <= i; k++) {
                            x[0].push_back(v[0][k]);
                        }
                        for (int k = j + 1; k < v[1].size(); k++) {
                            x[1].push_back(v[1][k]);
                        }
                        for (int k = 0; k <= j; k++) {
                            x[1].push_back(v[1][k]);
                        }
                        reverse(x[1].begin(), x[1].end());
                        vector<int> ans = x[0];
                        for (auto k : x[1]) {
                            ans.push_back(k);
                        }
                        return ans;
                    }
                }
            }
            if (v[0].size() > v[1].size()) {
                return v[0];
            } else {
                return v[1];
            }*/
        }
    }
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if (i == v[0].size()) {
      |                 ~~^~~~~~~~~~~~~~
longesttrip.cpp:117:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             for (int k = i + 1; k < v[0].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~
longesttrip.cpp:123:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for (int k = j + 1; k < v[1].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

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 0 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 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 6 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 600 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 4 ms 600 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 6 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 608 KB Output is correct
11 Correct 4 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 20 ms 344 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 5 ms 344 KB Output is correct
19 Correct 5 ms 436 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 4 ms 344 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 7 ms 344 KB Output is correct
24 Correct 5 ms 344 KB Output is correct
25 Correct 13 ms 344 KB Output is correct
26 Correct 13 ms 344 KB Output is correct
27 Correct 8 ms 344 KB Output is correct
28 Correct 9 ms 344 KB Output is correct
29 Correct 8 ms 344 KB Output is correct
30 Correct 5 ms 344 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 8 ms 344 KB Output is correct
33 Correct 5 ms 344 KB Output is correct
34 Correct 5 ms 600 KB Output is correct
35 Correct 5 ms 344 KB Output is correct
36 Correct 5 ms 344 KB Output is correct
37 Correct 5 ms 608 KB Output is correct
38 Correct 5 ms 608 KB Output is correct
39 Correct 6 ms 344 KB Output is correct
40 Correct 9 ms 344 KB Output is correct
41 Correct 8 ms 600 KB Output is correct
42 Correct 8 ms 600 KB Output is correct
43 Correct 8 ms 344 KB Output is correct
44 Correct 6 ms 344 KB Output is correct
45 Correct 8 ms 344 KB Output is correct
46 Correct 9 ms 344 KB Output is correct
47 Correct 7 ms 344 KB Output is correct
48 Correct 8 ms 340 KB Output is correct
49 Correct 9 ms 340 KB Output is correct
50 Correct 5 ms 344 KB Output is correct
51 Correct 8 ms 432 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 600 KB Output is correct
55 Correct 6 ms 344 KB Output is correct
56 Correct 6 ms 884 KB Output is correct
57 Correct 6 ms 440 KB Output is correct
58 Correct 7 ms 612 KB Output is correct
59 Correct 6 ms 600 KB Output is correct
60 Correct 6 ms 600 KB Output is correct
61 Correct 7 ms 344 KB Output is correct
62 Correct 7 ms 608 KB Output is correct
63 Correct 8 ms 688 KB Output is correct
64 Correct 7 ms 608 KB Output is correct

Subtask #4
45.0 / 60.0

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