Submission #1001331

#TimeUsernameProblemLanguageResultExecution timeMemory
1001331spacewalkerLongest Trip (IOI23_longesttrip)C++17
5 / 100
7 ms424 KiB
#include <bits/stdc++.h> #include "longesttrip.h" using namespace std; optional<int> find_edge_between(vector<int> s, int v) { if (!are_connected(s, {v})) return nullopt; vector<int> current = s; while (current.size() > 1) { int hs = current.size() / 2; vector<int> h1(begin(current), begin(current) + hs), h2(begin(current) + hs, end(current)); if (are_connected(h1, {v})) current = h1; else current = h2; } return current[0]; } optional<pair<int, int>> find_edge_between(vector<int> s1, vector<int> s2) { if (!are_connected(s1, s2)) return nullopt; vector<int> current = s1; while (current.size() > 1) { int hs = current.size() / 2; vector<int> h1(begin(current), begin(current) + hs), h2(begin(current) + hs, end(current)); if (are_connected(h1, s2)) current = h1; else current = h2; } return make_pair(current[0], find_edge_between(s2, current[0]).value()); } std::vector<int> longest_trip(int N, int D) { deque<int> p1{0}, p2; for (int i = 1; i < N; ++i) { if (are_connected({p1.back()}, {i})) { p1.push_back(i); } else if (!p2.empty()) { p2.push_front(i); } else { p2.push_back(i); } } vector<int> fp1(p1.begin(), p1.end()), fp2(p2.begin(), p2.end()); if (fp1.size() == N) return fp1; if (!are_connected({fp2.front()}, {fp2.back()})) { vector<int> ans = fp1; reverse(begin(fp2), end(fp2)); ans.insert(end(ans), begin(fp2), end(fp2)); return ans; } if (!are_connected({fp1.front()}, {fp1.back()})) { vector<int> ans = fp2; reverse(begin(fp2), end(fp2)); ans.insert(end(ans), begin(fp1), end(fp1)); return ans; } auto bridge = find_edge_between(fp1, fp2); if (!bridge) { return fp1.size() > fp2.size() ? fp1 : fp2; } auto left_end_iter = find(begin(fp2), end(fp2), bridge->second); rotate(begin(fp2), left_end_iter, end(fp2)); auto right_end_iter = find(begin(fp1), end(fp1), bridge->first); rotate(begin(fp1), right_end_iter, end(fp1)); vector<int> ans = fp2; reverse(begin(ans), end(ans)); ans.insert(end(ans), begin(fp1), end(fp1)); return ans; }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:42:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |   if (fp1.size() == N) return fp1;
      |       ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...