Submission #961753

#TimeUsernameProblemLanguageResultExecution timeMemory
961753Prieved1Longest Trip (IOI23_longesttrip)C++17
15 / 100
36 ms3952 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; int cnt=0; int n; map<int, map<int,int>> mp; bool query1(int a, int b) { if(mp[a][b]!=0)return mp[a][b]-1; int c=are_connected({a}, {b}); mp[a][b]=c+1; mp[b][a]=c+1; cnt++; return c; } bool query2(int a, int b) { for(int j = 0;j<n;j++) { if(a==j or j==b)continue; if(mp[a][j]==1 and mp[j][b]==1) { mp[a][b]=2; mp[b][a]=2; return 1; } } return query1(a,b); } vector<int> longest_trip(int N, int D) { n=N; cnt=0; mp.clear(); srand(time(NULL)); vector<int> id(N); iota(id.begin(), id.end(), 0); random_shuffle(id.begin(), id.end()); vector<int> t[2]; t[0].push_back(id[0]); t[1].push_back(id[1]); bool connected=1; for(int ii = 2;ii<N;ii++) { int i=id[ii]; if(t[0].size() < t[1].size())swap(t[0], t[1]); if(t[1].size()>0 and rand()%2) { swap(t[0], t[1]); } if(query2(i, t[0].back())) { t[0].push_back(i); connected=1; } else if(connected==false or query2(i, t[1].back())) { t[1].push_back(i); connected=false; } else { connected=0; while(t[1].size()) { t[0].push_back(t[1].back()); t[1].pop_back(); } t[1].push_back(i); } } assert(cnt<380); if(t[0].size()<t[1].size())swap(t[0], t[1]); if(t[1].size()==0)return t[0]; if(query2(t[0][0], t[1].back())) { reverse(t[0].begin(), t[0].end()); while(t[1].size()) { t[0].push_back(t[1].back()); t[1].pop_back(); } return t[0]; } if(query2(t[0][0], t[1][0])) { reverse(t[0].begin(), t[0].end()); reverse(t[1].begin(), t[1].end()); while(t[1].size()) { t[0].push_back(t[1].back()); t[1].pop_back(); } return t[0]; } if(query2(t[0].back(), t[1][0])) { reverse(t[1].begin(), t[1].end()); while(t[1].size()) { t[0].push_back(t[1].back()); t[1].pop_back(); } return t[0]; } if(are_connected(t[0], t[1])==false)return t[0]; int lo = 0, hi = t[0].size()-1; int res=hi; while(lo <= hi) { int mid=(lo+hi)/2; vector<int> tmp; for(int j = 0;j<=mid;j++)tmp.push_back(t[0][j]); if(are_connected(tmp, t[1])) { res=mid; hi=mid-1; } else{ lo=mid+1; } } lo=0, hi=t[1].size()-1; int res2=hi; while(lo <= hi) { int mid=(lo+hi)/2; vector<int> tmp; for(int j = 0;j<=mid;j++)tmp.push_back(t[1][j]); if(are_connected(tmp, {t[0][res]})) { res2=mid; hi=mid-1; } else{ lo=mid+1; } } vector<int> ans; for(int j = res+1;j<t[0].size();j++) { ans.push_back(t[0][j]); } for(int j = 0;j<=res;j++)ans.push_back(t[0][j]); for(int j = res2;j<t[1].size();j++)ans.push_back(t[1][j]); for(int j = 0;j<res2;j++)ans.push_back(t[1][j]); return ans; }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:120:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |       for(int j = res+1;j<t[0].size();j++) {
      |                         ~^~~~~~~~~~~~
longesttrip.cpp:124:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |       for(int j = res2;j<t[1].size();j++)ans.push_back(t[1][j]);
      |                        ~^~~~~~~~~~~~
#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...