Submission #1228079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228079		rxlfd314	가장 긴 여행 (IOI23_longesttrip)	C++17	85 / 100	8 ms	444 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_(const int l = 0, const int r = INT_MAX) {
  return uniform_int_distribution<int>(l, r)(rng);
}

bool query(const vt<int> A, const vt<int> B) {
  return are_connected(A, B);
}

vt<int> longest_trip(int N, int D) {
  vt<int> ord(N);
  iota(all(ord), 0);
  shuffle(all(ord), rng);
  vt<int> line_a = {ord[0]}, line_b;
  FOR(i, 1, N-1) {
    if (rand_() & 1 && size(line_b))
      swap(line_a, line_b);
    if (query({line_a.back()}, {ord[i]})) {
      line_a.push_back(ord[i]);
    } else if (!size(line_b) || query({line_b.back()}, {ord[i]})) {
      line_b.push_back(ord[i]);
    } else {
      reverse(all(line_b));
      line_a.insert(line_a.end(), all(line_b));
      line_b = {ord[i]};
    }
  }
  if (!size(line_b))
    return line_a;
  FOR(i, 0, 3) {
    if (query({line_a[0]}, {line_b[0]})) {
      reverse(all(line_a));
      line_a.insert(line_a.end(), all(line_b));
      return line_a;
    }
    reverse(all(line_b));
    if (i & 1)
      reverse(all(line_a));
  }
  const auto check = [&](const vt<int> A, const vt<int> B) {
    int lo = 0, hi = size(A);
    while (lo < hi) {
      const int mid = lo + hi >> 1;
      if (query(vt<int>(A.begin(), A.begin() + mid + 1), B))
        hi = mid;
      else
        lo = mid + 1;
    }
    return lo;
  };
  const int a = check(line_a, line_b);
  if (a == size(line_a))
    return size(line_a) > size(line_b) ? line_a : line_b;
  const int b = check(line_b, {line_a[a]});
  rotate(line_a.begin(), line_a.begin() + a + 1, line_a.end());
  rotate(line_b.begin(), line_b.begin() + b, line_b.end());
  line_a.insert(line_a.end(), all(line_b));
  return line_a;
}

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