Submission #852649

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
852649	2023-09-22T10:04:08 Z	aZvezda	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	15 ms	856 KB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

vector<int> longest_trip(int N, int D) {
	vector<int> p1, p2;
	p1.push_back(N - 1);
	if (N % 2 == 0) {
		if (are_connected({N - 2}, {N - 1})) {
			p1.push_back(N - 2);
		} else {
			p2.push_back(N - 2);
		}
	}
	for (int i = 0; i < N - 2; i += 2) {
		if (sz(p2) == 0) {
			bool v1 = are_connected({i}, {i + 1});
			bool v2 = are_connected({p1.back()}, {i});
			bool v3 = are_connected({p1.back()}, {i + 1});
			if (v1) {
				if (v2) {
					p1.push_back(i);
					p1.push_back(i + 1);
				} else if (v3) {
					p1.push_back(i + 1);
					p1.push_back(i);
				} else {
					p2.push_back(i);
					p2.push_back(i + 1);
				}
			} else {
				if (v2) {
					p1.push_back(i);
					p2.push_back(i + 1);
				} else {
					p2.push_back(i);
					p1.push_back(i + 1);
				}
			}
		} else {
			int v = i, w = i + 1;
			bool v1 = are_connected({v}, {w});
			if (v1) {
				if (!are_connected({p1.back()}, {v}))
					swap(p1, p2);
				if (are_connected({p2.back()}, {w})) {
					p1.push_back(v);
					p1.push_back(w);
					for (int i = sz(p2) - 1; i >= 0; i--)
						p1.push_back(p2[i]);
					p2.clear();
				} else {
					p1.push_back(v);
					p1.push_back(w);
				}
			} else {
				if (!are_connected({p1.back()}, {v}))
					swap(p1, p2);
				if (are_connected({p2.back()}, {w})) {
					p1.push_back(v);
					p2.push_back(w);
				} else {
					p1.push_back(w);
					p2.push_back(v);
				}
			}
		}
	}
	if (sz(p1) < sz(p2))
		swap(p1, p2);
	if (sz(p2) == 0)
		return p1;
	if (!are_connected(p1, p2)) {
		return p1;
	}
	if ((sz(p1) <= 2 || are_connected({p1.front()}, {p1.back()})) && (sz(p2) <= 2 || are_connected({p2.front()}, {p2.back()}))) {
		int s1 = 0, e1 = sz(p1);
		int s2 = 0, e2 = sz(p2);
		while (e2 - s2 > 1) {
			int m2 = (s2 + e2) / 2;
			vector<int> q(p2.begin() + s2, p2.begin() + m2);
			if (are_connected(p1, q))
				e2 = m2;
			else
				s2 = m2;
		}
		while (e1 - s1 > 1) {
			int m1 = (s1 + e1) / 2;
			vector<int> q(p1.begin() + s1, p1.begin() + m1);
			if (are_connected(q, {p2[s2]}))
				e1 = m1;
			else
				s1 = m1;
		}
		rotate(p1.begin(), p1.begin() + s1, p1.end());
		rotate(p2.begin(), p2.begin() + s2, p2.end());
		reverse(all(p2));
		for (auto &x : p1)
			p2.push_back(x);
		return p2;
	}
	if (are_connected({p1[0]}, {p2[0]})) {
		reverse(all(p2));
		for (auto &x : p1)
			p2.push_back(x);
		return p2;
	}
	if (are_connected({p1[0]}, {p2.back()})) {
		for (auto &x : p1)
			p2.push_back(x);
		return p2;
	}
	if (are_connected({p1.back()}, {p2[0]})) {
		for (auto &x : p2)
			p1.push_back(x);
		return p1;
	}
	if (are_connected({p1.back()}, {p2.back()})) {
		reverse(all(p2));
		for (auto &x : p2)
			p1.push_back(x);
		return p1;
	}
	assert(0);
}

Subtask #0

0.0 / 0.0

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

Subtask #3

25.0 / 25.0

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