Submission #1074204

#TimeUsernameProblemLanguageResultExecution timeMemory
1074204anangoLongest Trip (IOI23_longesttrip)C++17
15 / 100
18 ms600 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; int n; bool are_connected_valid(vector<int> S, vector<int> T) { sort(S.begin(), S.end()); sort(T.begin(), T.end()); //assert(S.size()>0); //assert(T.size()>0); if (S.size()==0 || T.size()==0) { return 0; } return are_connected(S,T); } 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_valid({path1.back()},{i})) { path1.push_back(i); } else if (are_connected_valid({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_valid(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_valid(end1,end2)) { if (are_connected_valid({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_valid({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_valid({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_valid({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 } } assert(grp1.size()!=1 && grp2.size()!=1); int l = 0; int r = grp1.size(); while (l<r) { int m = (l+r)/2; vector<int> part(grp1.begin(), grp1.begin()+m); if (are_connected_valid(part,grp2)) { r=m; } else { l=m+1; } } int x1 = l; l = 0; r = grp2.size(); while (l<r) { int m = (l+r)/2; vector<int> part(grp2.begin(), grp2.begin()+m); if (are_connected_valid({grp1[x1]},part)) { r=m; } else { l=m+1; } } int x2 = l; //assert(x1!=0 && x2!=0 && x1+1!=grp1.size() && x2+1!=grp2.size()); 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]); } assert(ans.size()==n && grp1.size()+grp2.size()==n); return ans; }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i=x1+1; i<grp1.size(); i++) {
      |                      ~^~~~~~~~~~~~
longesttrip.cpp:134:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i=x2; i<grp2.size(); i++) {
      |                    ~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from longesttrip.cpp:2:
longesttrip.cpp:140:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |     assert(ans.size()==n && grp1.size()+grp2.size()==n);
      |            ~~~~~~~~~~^~~
longesttrip.cpp:140:52: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |     assert(ans.size()==n && grp1.size()+grp2.size()==n);
      |                             ~~~~~~~~~~~~~~~~~~~~~~~^~~
#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...