Submission #1074164

#TimeUsernameProblemLanguageResultExecution timeMemory
1074164anangoLongest Trip (IOI23_longesttrip)C++17
15 / 100
14 ms600 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; int n; vector<int> longest_trip(int N, int D) { n=N; deque<int> path1; deque<int> path2; path1.push_back(0); path2.push_back(1); for (int i=2; i<n; i++) { if (are_connected({path1.back()},{i})) { path1.push_back(i); } else if (are_connected({path2.back()},{i})) { path2.push_back(i); } else { //path1's end is connected to path2's end while (path2.size()) { path1.push_back(path2.back()); path2.pop_back(); } path2={i}; } } vector<int> grp1(path1.begin(), path1.end()); vector<int> grp2(path2.begin(), path2.end()); //cout << "JAMBLOAT" << " " << grp1.size() <<" " << grp2.size() << endl; if (grp1.size()<grp2.size()) { swap(grp1,grp2); } if (grp1.size()==0 || grp2.size()==0 || !are_connected(grp1,grp2)) { return grp1; } vector<int> end1 = {grp1.front(), grp1.back()}; vector<int> end2 = {grp2.front(), grp2.back()}; end1.erase(unique(end1.begin(), end1.end()),end1.end()); end2.erase(unique(end2.begin(), end2.end()),end2.end()); if (are_connected(end1,end2)) { if (are_connected({grp1.front()},{grp2.front()})) { vector<int> con; for (auto i:grp1) { con.push_back(i); } reverse(con.begin(), con.end()); for (auto i:grp2) { con.push_back(i); } return con; //length n } if (are_connected({grp1.front()},{grp2.back()})) { vector<int> con; for (auto i:grp1) { con.push_back(i); } reverse(con.begin(), con.end()); reverse(grp2.begin(), grp2.end()); for (auto i:grp2) { con.push_back(i); } return con; //length n } if (are_connected({grp1.back()},{grp2.front()})) { vector<int> con; for (auto i:grp1) { con.push_back(i); } for (auto i:grp2) { con.push_back(i); } return con; //length n } if (are_connected({grp1.back()},{grp2.back()})) { vector<int> con; for (auto i:grp1) { con.push_back(i); } reverse(grp2.begin(), grp2.end()); for (auto i:grp2) { con.push_back(i); } return con; //length n } } int l = 0; int r = grp1.size(); r--; while (l<r) { int m = (l+r)/2; vector<int> part(grp1.begin(), grp1.begin()+m); if (are_connected(part,grp2)) { r=m; } else { l=m+1; } } int x1 = l; l = 0; r = grp2.size(); r--; while (l<r) { int m = (l+r)/2; vector<int> part(grp2.begin(), grp2.begin()+m); if (are_connected({grp1[x1]},part)) { r=m; } else { l=m+1; } } int x2 = l; // vector<int> ans; for (int i=x1+1; i<grp1.size(); i++) { ans.push_back(grp1[i]); } for (int i=0; i<=x1; i++) { ans.push_back(grp1[i]); } for (int i=x2; i<grp2.size(); i++) { ans.push_back(grp2[i]); } for (int i=0; i<x2; i++) { ans.push_back(grp2[i]); } return ans; }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i=x1+1; i<grp1.size(); i++) {
      |                      ~^~~~~~~~~~~~
longesttrip.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i=x2; i<grp2.size(); i++) {
      |                    ~^~~~~~~~~~~~
#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...