Submission #997177

#	Time	Username	Problem	Language	Result	Execution time	Memory
997177		kunzaZa183	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	12 ms	640 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int N, int D) {
  vector<int> trip1(1, 0), trip2(1, 1);

  int state = 2;
  int num1;

  for (int i = 2; i < N; i++) {
    if (state == 0) {
      if (are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)))
        trip2.push_back(i);
      else
        trip1.insert(trip1.begin() + num1, i);
      state = 2;
    } else if (state == 1) {
      if (are_connected(vector<int>(1, trip1.back()), vector<int>(1, i)))
        trip1.push_back(i);
      else
        trip2.push_back(i);
      state = 2;
    } else if (state == 2) {
      bool b1 = are_connected(vector<int>(1, trip1.back()), vector<int>(1, i)),
           b2 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
      if (b1 && b2) {
        reverse(trip2.begin(), trip2.end());
        trip1.push_back(i);
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
        if (i == N - 1) return trip1;
        i++;
        trip2.push_back(i);
      } else if (b1) {
        trip1.push_back(i);
        state = 1;
      } else if (b2) {
        trip2.push_back(i);
        state = 1;
      } else {
        num1 = trip1.size();
        reverse(trip2.begin(), trip2.end());
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
        trip2.push_back(i);
        state = 0;
      }
    }
  }

  if (trip2.empty()) return trip1;
  if (are_connected(trip1, trip2)) {
    // vector<int> vi, vi2;
    // if (trip1.size() != 1)
    //   vi.push_back(trip1.front()), vi.push_back(trip1.back());
    // else
    //   vi.push_back(trip1.front());
    // if (trip2.size() != 1)
    //   vi2.push_back(trip2.front()), vi2.push_back(trip2.back());
    // else
    //   vi2.push_back(trip2.front());
    // if (are_connected(vi, vi2)) {
    //   while (1) {
    //   }
    // }

    // if (trip1.size() != 1) {
    //   if (!are_connected(vector<int>(1, trip1.front()),
    //                      vector<int>(1, trip1.back())))

    //     while (1) {
    //     }
    // }
    // if (trip2.size() != 1) {
    //   if (!are_connected(vector<int>(1, trip2.front()),
    //                      vector<int>(1, trip2.back())))

    //     while (1) {
    //     }
    // }

    vector<int> vi, vi2;
    if (trip1.size() != 1)
      vi.push_back(trip1.front()), vi.push_back(trip1.back());
    else
      vi.push_back(trip1.front());
    if (trip2.size() != 1)
      vi2.push_back(trip2.front()), vi2.push_back(trip2.back());
    else
      vi2.push_back(trip2.front());
    if (are_connected(vi, vi2)) {
      vector<int> ans;
      if (are_connected(vector<int>(1, trip1.front()),
                        vector<int>(1, trip2.front())))
        reverse(trip1.begin(), trip1.end());
      else if (are_connected(vector<int>(1, trip1.front()),
                             vector<int>(1, trip2.back())))
        trip1.swap(trip2);
      else if (are_connected(vector<int>(1, trip1.back()),
                             vector<int>(1, trip2.front()))) {
      } else if (are_connected(vector<int>(1, trip1.back()),
                               vector<int>(1, trip2.back())))
        reverse(trip2.begin(), trip2.end());

      for (auto a : trip1) ans.push_back(a);
      for (auto a : trip2) ans.push_back(a);
      return ans;
    }

    int l = 0, r = int(trip1.size()) - 1;
    while (l < r) {
      int mid = (l + r) / 2;
      vector<int> tmp;
      for (int i = l; i <= mid; i++) tmp.push_back(trip1[i]);
      if (are_connected(tmp, trip2))
        r = mid;
      else
        l = mid + 1;
    }
    int firstone = l;
    l = 0, r = int(trip2.size()) - 1;
    while (l < r) {
      int mid = (l + r) / 2;
      vector<int> tmp;
      for (int i = l; i <= mid; i++) tmp.push_back(trip2[i]);
      if (are_connected(tmp, vector<int>(1, trip1[firstone])))
        r = mid;
      else
        l = mid + 1;
    }
    int secondone = l;
    vector<int> ans;
    for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
    for (int i = 0; i <= firstone; i++) ans.push_back(trip1[i]);
    for (int i = secondone; i < trip2.size(); i++) ans.push_back(trip2[i]);
    for (int i = 0; i < secondone; i++) ans.push_back(trip2[i]);
    return ans;
  }

  if (trip1.size() < trip2.size()) trip1.swap(trip2);
  return trip1;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:135:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
      |                                ~~^~~~~~~~~~~~~~
longesttrip.cpp:137:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i = secondone; i < trip2.size(); i++) ans.push_back(trip2[i]);
      |                             ~~^~~~~~~~~~~~~~

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