Submission #941914

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
941914	2024-03-09 16:51:20	benjaminkleyn	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	12 ms	944 KiB

longesttrip

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std; 
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define C are_connected
#define pb push_back
#define bk back
#define rev(x) reverse(all(x)) 
vi longest_trip(int N, int D){if (D == 3){vi r(N);iota(all(r), 0);return r;} if (D == 2){vi r;int t;if (C({0}, {1}))r = {0, 1}, t = 2;else r = {0, 2, 1}, t = 3; for (int i = t; i < N; i++){if (!C({r.bk()}, {i}))rev(r);r.pb(i);} return r;} vi A = {0}, B = {1};for (int i = 2; i + 1 < N; i += 2){if (C({i}, {i + 1})){if (C({i}, {A.bk(), B.bk()})){if (C({i}, {A.bk()})){A.pb(i);A.pb(i + 1);}else{B.pb(i);B.pb(i + 1);}}else{rev(B);for (int x : B) A.pb(x);B = {i, i + 1};}}else{if (C({A.bk()}, {i})){A.pb(i);if (C({B.bk()}, {i + 1}))B.pb(i + 1);else{rev(B);for (int x : B)A.pb(x);B = {i + 1};}}else{A.pb(i + 1);if (C({B.bk()}, {i}))B.pb(i);else{rev(B);for (int x : B)A.pb(x);B = {i};}}}}if (N % 2){if (C({N - 1}, {A.bk(), B.bk()})){if (C({N - 1}, {A.bk()}))A.pb(N - 1);else B.pb(N - 1);}else{rev(B);for (int x : B)A.pb(x);B = {N - 1};}}if (!C(A, B)){if (A.size() > B.size())return A;return B;}if (A.size() > 1 && !C({A[0]}, {A.bk()})){if (C({A.bk()}, {B.bk()}))rev(A);for (int x : A)B.pb(x);return B;}if (B.size() > 1 && !C({B[0]}, {B.bk()})){if (C({A.bk()}, {B.bk()}))rev(B);for (int x : B)A.pb(x);return A;}auto s = [](vi X, vi Y){int a = 1, b = X.size();while (a < b){int m = (a + b) / 2;if (C(vi(X.begin(), X.begin() + m), Y))b = m;else a = m + 1;}return a - 1;};int x = s(A, B);int y = s(B, {A[x]});vi r;for (int i = x + 1; i <= x + A.size(); i++)r.pb(A[i % A.size()]);for (int i = y; i < y + B.size(); i++)r.pb(B[i % B.size()]);return r;}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:10:1327: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | vi longest_trip(int N, int D){if (D == 3){vi r(N);iota(all(r), 0);return r;} if (D == 2){vi r;int t;if (C({0}, {1}))r = {0, 1}, t = 2;else r = {0, 2, 1}, t = 3; for (int i = t; i < N; i++){if (!C({r.bk()}, {i}))rev(r);r.pb(i);} return r;} vi A = {0}, B = {1};for (int i = 2; i + 1 < N; i += 2){if (C({i}, {i + 1})){if (C({i}, {A.bk(), B.bk()})){if (C({i}, {A.bk()})){A.pb(i);A.pb(i + 1);}else{B.pb(i);B.pb(i + 1);}}else{rev(B);for (int x : B) A.pb(x);B = {i, i + 1};}}else{if (C({A.bk()}, {i})){A.pb(i);if (C({B.bk()}, {i + 1}))B.pb(i + 1);else{rev(B);for (int x : B)A.pb(x);B = {i + 1};}}else{A.pb(i + 1);if (C({B.bk()}, {i}))B.pb(i);else{rev(B);for (int x : B)A.pb(x);B = {i};}}}}if (N % 2){if (C({N - 1}, {A.bk(), B.bk()})){if (C({N - 1}, {A.bk()}))A.pb(N - 1);else B.pb(N - 1);}else{rev(B);for (int x : B)A.pb(x);B = {N - 1};}}if (!C(A, B)){if (A.size() > B.size())return A;return B;}if (A.size() > 1 && !C({A[0]}, {A.bk()})){if (C({A.bk()}, {B.bk()}))rev(A);for (int x : A)B.pb(x);return B;}if (B.size() > 1 && !C({B[0]}, {B.bk()})){if (C({A.bk()}, {B.bk()}))rev(B);for (int x : B)A.pb(x);return A;}auto s = [](vi X, vi Y){int a = 1, b = X.size();while (a < b){int m = (a + b) / 2;if (C(vi(X.begin(), X.begin() + m), Y))b = m;else a = m + 1;}return a - 1;};int x = s(A, B);int y = s(B, {A[x]});vi r;for (int i = x + 1; i <= x + A.size(); i++)r.pb(A[i % A.size()]);for (int i = y; i < y + B.size(); i++)r.pb(B[i % B.size()]);return r;}
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             ~~^~~~~~~~~~~~~~~
longesttrip.cpp:10:1388: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | vi longest_trip(int N, int D){if (D == 3){vi r(N);iota(all(r), 0);return r;} if (D == 2){vi r;int t;if (C({0}, {1}))r = {0, 1}, t = 2;else r = {0, 2, 1}, t = 3; for (int i = t; i < N; i++){if (!C({r.bk()}, {i}))rev(r);r.pb(i);} return r;} vi A = {0}, B = {1};for (int i = 2; i + 1 < N; i += 2){if (C({i}, {i + 1})){if (C({i}, {A.bk(), B.bk()})){if (C({i}, {A.bk()})){A.pb(i);A.pb(i + 1);}else{B.pb(i);B.pb(i + 1);}}else{rev(B);for (int x : B) A.pb(x);B = {i, i + 1};}}else{if (C({A.bk()}, {i})){A.pb(i);if (C({B.bk()}, {i + 1}))B.pb(i + 1);else{rev(B);for (int x : B)A.pb(x);B = {i + 1};}}else{A.pb(i + 1);if (C({B.bk()}, {i}))B.pb(i);else{rev(B);for (int x : B)A.pb(x);B = {i};}}}}if (N % 2){if (C({N - 1}, {A.bk(), B.bk()})){if (C({N - 1}, {A.bk()}))A.pb(N - 1);else B.pb(N - 1);}else{rev(B);for (int x : B)A.pb(x);B = {N - 1};}}if (!C(A, B)){if (A.size() > B.size())return A;return B;}if (A.size() > 1 && !C({A[0]}, {A.bk()})){if (C({A.bk()}, {B.bk()}))rev(A);for (int x : A)B.pb(x);return B;}if (B.size() > 1 && !C({B[0]}, {B.bk()})){if (C({A.bk()}, {B.bk()}))rev(B);for (int x : B)A.pb(x);return A;}auto s = [](vi X, vi Y){int a = 1, b = X.size();while (a < b){int m = (a + b) / 2;if (C(vi(X.begin(), X.begin() + m), Y))b = m;else a = m + 1;}return a - 1;};int x = s(A, B);int y = s(B, {A[x]});vi r;for (int i = x + 1; i <= x + A.size(); i++)r.pb(A[i % A.size()]);for (int i = y; i < y + B.size(); i++)r.pb(B[i % B.size()]);return r;}
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ~~^~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60