Submission #1060390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060390		mychecksedad	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	7 ms	344 KiB

longesttrip

#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);

  vi A(all(a));
  vi B(all(b));

  if(are_connected(A, B) == 0){
    return A;
  }

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

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60