Submission #1061033

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1061033	2024-08-16T05:46:44 Z	mychecksedad	Longest Trip (IOI23_longesttrip)	C++17	Compilation error	0 ms	0 KB

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{b.back()}, vi{i})){
      b.pb(i);
    }else if(are_connected(vi{a.back()}, vi{i})){
      a.pb(i);
    }else{
      if(b.empty()) b.pb(i);
      else{
        for(int x: b) a.pb(x);
        b.clear();
        b.pb(i);
      }
    }
  }
  if(b.size()>a.size())swap(a,b);
 
  vi A(all(a));
  vi B(all(b));
 
  if(B.empty()) return A;
 
  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){
        reverse(all(b));
        for(int x: b) a.push_front(x);
      }else{
        reverse(all(b));
        for(int x: b) a.pb(x);
      }
      break;
    }else{
      int vl = 0, vr = int(b.size()) - 1, ub = -1; vi aa(all(a));
      while(ul <= ur){
        int um = ul+ur>>1;
        vi z;
        for(int j = 0; j <= um; ++j) z.pb(b[j]);
        if(are_connected(z, a)){
          ub = um;
          ur = um - 1;
        }else ul = um + 1;
      }
      if(ub == -1) return a;
      int ul = 0, ur = int(a.size()) - 1, ua = -1;
      while(ul <= ur){
        int um = ul+ur>>1;
        vi z;
        for(int j = 0; j <= um; ++j) z.pb(a[j]);
        if(are_connected(z, vi{b[ub]})){
          ua = um;x
          ur = um - 1;
        }else ul = um + 1;
      }
      if(ua == -1){
        vi res(all(a));
        return res;
      }
      int uu = b[ub];
      while(b.front() != uu){
        int x = b.front();
        b.pop_front();
        b.pb(x);
      }
      u = a[ua];
      while(a.front() != u){
        int x = a.front();
        a.pop_front();
        a.pb(x);
      }
      reverse(all(b));
      for(int x: b) a.push_front(x);
      break;
    }
  }
  vi res(all(a));
  return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:79:18: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |   while(a.size() < n){
      |         ~~~~~~~~~^~~
longesttrip.cpp:91:13: error: 'ul' was not declared in this scope; did you mean 'ub'?
   91 |       while(ul <= ur){
      |             ^~
      |             ub
longesttrip.cpp:91:19: error: 'ur' was not declared in this scope; did you mean 'ub'?
   91 |       while(ul <= ur){
      |                   ^~
      |                   ub
longesttrip.cpp:95:29: error: could not convert 'a' from 'std::deque<int>' to 'std::vector<int>'
   95 |         if(are_connected(z, a)){
      |                             ^
      |                             |
      |                             std::deque<int>
longesttrip.cpp:100:27: error: could not convert 'a' from 'std::deque<int>' to 'std::vector<int>'
  100 |       if(ub == -1) return a;
      |                           ^
      |                           |
      |                           std::deque<int>
longesttrip.cpp:103:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         int um = ul+ur>>1;
      |                  ~~^~~
longesttrip.cpp:107:19: error: 'x' was not declared in this scope
  107 |           ua = um;x
      |                   ^
longesttrip.cpp:90:11: warning: unused variable 'vl' [-Wunused-variable]
   90 |       int vl = 0, vr = int(b.size()) - 1, ub = -1; vi aa(all(a));
      |           ^~
longesttrip.cpp:90:19: warning: unused variable 'vr' [-Wunused-variable]
   90 |       int vl = 0, vr = int(b.size()) - 1, ub = -1; vi aa(all(a));
      |                   ^~
longesttrip.cpp:77:15: warning: unused variable 'v' [-Wunused-variable]
   77 |   int u = -1, v;
      |               ^