답안 #1033192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033192	2024-07-24T14:03:54 Z	TAhmed33	가장 긴 여행 (IOI23_longesttrip)	C++17	100 / 100	13 ms	600 KB

longesttrip

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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