Submission #1060389

#TimeUsernameProblemLanguageResultExecution timeMemory
1060389mychecksedadLongest Trip (IOI23_longesttrip)C++17
15 / 100
293 ms600 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define ll long long #define ff first #define ss second #define vi vector<int> const int N = 200005; std::vector<int> longest_trip(int n, int D) { if(D == 3){ vector<int> v; for(int i = 0; i < n; ++i) v.pb(i); return v; } if(D == 2){ deque<int> v; v.pb(0); int o = -1; for(int i = 1; i < n; ++i){ bool x = are_connected(vi{0}, vi{i}); if(x){ o = i; v.pb(i); break; } } if(o == -1){ vi res; for(int i = 1; i < n; ++i){ res.pb(i); } return res; } for(int i = 1; i < n; ++i){ if(o == i) continue; bool x = are_connected(vi{v[0]}, vi{i}); if(x){ v.push_front(i); }else v.pb(i); } vector<int> res(all(v)); return res; } vector<vector<int>> g(n); deque<int> a, b; a.pb(0); for(int i = 1; i < n; ++i){ if(are_connected(vi{a[0]}, vi{i})){ a.push_front(i); }else if(are_connected(vi{a.back()}, vi{i})){ a.pb(i); }else{ if(b.empty()) b.pb(i); else{ if(are_connected(vi{b[0]}, vi{i})){ b.push_front(i); }else if(are_connected(vi{b.back()}, vi{i})){ b.pb(i); }else{ if(are_connected(vi{a.back()}, vi{b[0]})){ for(int x: b) a.pb(x); b.clear(); b.pb(i); }else{ assert(false); } } } } } if(b.size()>a.size())swap(a,b); int u = -1, v; while(a.size() < n){ if(are_connected(vi{a[0]}, vi{a.back()}) == 0){ if(are_connected(vi{a[0]}, vi{b.back()}) == 1){ a.push_front(b.back()); b.pop_back(); }else{ a.pb(b.back()); b.pop_back(); } }else{ if(u == -1){ for(int i = 0; i < a.size(); ++i){ for(int j = i + 1; j < a.size(); ++j){ if(are_connected(vi{a[i]}, vi{a[j]}) == 0){ u = a[i], v = a[j]; break; } } if(u != -1) break; } } if(u == -1){ vi res(all(a)); return res; } if(are_connected(vi{b.back()}, vi{u}) == 1){ int cc = 0; while(a.front() != u){ int x = a.front(); a.pop_front(); a.pb(x); if(cc>n) assert(false); ++cc; } a.push_front(b.back()); b.pop_back(); }else{ int cc = 0; while(a.front() != v){ int x = a.front(); a.pop_front(); a.pb(x); ++cc; if(cc>n) assert(false); } a.push_front(b.back()); b.pop_back(); } } } vi res(all(a)); return res; }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:80:18: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |   while(a.size() < n){
      |         ~~~~~~~~~^~~
longesttrip.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i = 0; i < a.size(); ++i){
      |                        ~~^~~~~~~~~~
longesttrip.cpp:92:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |           for(int j = i + 1; j < a.size(); ++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...