Submission #1301794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301794		dabesttiger	Fun Tour (APIO20_fun)	C++20	31 / 100	65 ms	16140 KiB

fun

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

vector<int> createFunTour(int N, int Q) {
  //int H = hoursRequired(0, N - 1);
  //int A = attractionsBehind(0, N - 1);
  //return std::vector<int>(N);
  if (N == 2) {
    return {0, 1};
  }
  vector<int> subtrees(N);
  subtrees[0] = N-1;
  for (int i = 1; i < N; i++) {
    subtrees[i] = attractionsBehind(0, i);
  }
  int temp = 0;
  for (int i = 1; i < N; i++) {
    if (subtrees[temp] > subtrees[i] and subtrees[i] >= (N+1)/2) {
      temp = i;
    }
  }
  int r = temp;
  //cout << subtrees[0] << " " << subtrees[1] << " " << subtrees[2] << " " << r << "\n";
  vector<pair<int, int>> dists;
  for (int i = 0; i < N; i++) {
    if (i == r) {
      continue;
    }
    dists.push_back({hoursRequired(r, i), i});
  }
  sort(dists.begin(), dists.end());
  vector<pair<int, int>> a, b, c;
  a.push_back({1, dists[0].second});
  b.push_back({1, dists[1].second});
  for (int i = 2; i < N-1; i++) {
    if (hoursRequired(dists[i].second, a[0].second) == dists[i].first-1) {
      a.push_back(dists[i]);
      //cout << "a: " << dists[i].first << dists[i].second << "\n";
    } else if (hoursRequired(dists[i].second, b[0].second) == dists[i].first-1) {
      b.push_back(dists[i]);
      //cout << "b: " << dists[i].first << dists[i].second << "\n";
    } else {
      c.push_back(dists[i]);
      //cout << "c: " << dists[i].first << dists[i].second << "\n";
    }
  }
  vector<int> ans;
  int branch = 0;
  if (!c.empty()) {
    while (c.size() + b.size() != a.size() and a.size() + c.size() != b.size() and a.size() + b.size() != c.size()) {
      if (branch == 0) {
        if (a.back().first >= b.back().first and a.back().first >= c.back().first) {
          branch = 1;
          ans.push_back(a.back().second);
          a.pop_back();
        } else if (b.back().first >= c.back().first and b.back().first >= a.back().first) {
          branch = 2;
          ans.push_back(b.back().second);
          b.pop_back();
        } else {
          branch = 3;
          ans.push_back(c.back().second);
          c.pop_back();
        }
      } else if (branch == 1) {
        if (b.back().first >= c.back().first) {
          branch = 2;
          ans.push_back(b.back().second);
          b.pop_back();
        } else {
          branch = 3;
          ans.push_back(c.back().second);
          c.pop_back();
        }
      } else if (branch == 2) {
        if (a.back().first >= c.back().first) {
          branch = 1;
          ans.push_back(a.back().second);
          a.pop_back();
        } else {
          branch = 3;
          ans.push_back(c.back().second);
          c.pop_back();
        }
      } else if (branch == 3) {
        if (a.back().first >= b.back().first) {
          branch = 1;
          ans.push_back(a.back().second);
          a.pop_back();
        } else {
          branch = 2;
          ans.push_back(b.back().second);
          b.pop_back();
        }
      }
    }

    if (a.size() == b.size() + c.size()) {
      for (auto i:c) {
        b.push_back(i);
      }
      sort(b.begin(), b.end());
      if (branch == 3) {
        branch = 2;
      }
    } else if (b.size() == a.size() + c.size()) {
      for (auto i:c) {
        a.push_back(i);
      }
      sort(a.begin(), a.end());
      if (branch == 3) {
        branch = 2;
      }
    } else {
      for (auto i:a) {
        b.push_back(i);
      }
      sort(b.begin(), b.end());
      a = c;
      if (branch == 1) {
        branch = 2;
      }
      if (branch == 3) {
        branch = 1;
      }
    }
  }
  if (branch == 0) {
    if (a.size() < b.size()) {
      branch = 1;
    } else {
      branch = 2;
    }
  }
  while (!a.empty() or !b.empty()) {
    if (branch == 1) {
      branch = 2;
      ans.push_back(b.back().second);
      b.pop_back();
    } else {
      branch = 1;
      ans.push_back(a.back().second);
      a.pop_back();
    }
  }
  /*cout << "final\n";
  for (auto i:ans) {
    cout << i << " ";
  }
  cout << "\n";*/
  ans.push_back(r);
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34