| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 466563 | flappybird | Fun Tour (APIO20_fun) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "fun.h"
#include <bits/stdc++.h>
#include <cassert>
#define e(v) ( ( (v).empty() ) ? (pair<int, int>(-1, -1) ) : ( (v)[(v).size()-1] ) )
using namespace std;
typedef int ll;
vector<int> createFunTour(int N, int Q) {
if (N == 2) {
vector<ll> v;
v.push_back(0);
v.push_back(1);
return v;
}
vector<ll> res;
ll i;
for (i = 0; i < N; i++) res.push_back(attractionsBehind(0, i));
ll c = 0;
ll mn = 1010101010;
for (i = 0; i < N; i++) {
if (res[i] >= (N + 1) / 2) {
if (mn > res[i]) mn = res[i], c = i;
}
}
vector<pair<ll, ll>> dis;
vector<vector<pair<ll, ll>>> subtree;
subtree.resize(3);
ll num;
for (i = 0; i < N; i++) {
if (i == c) continue;
dis.push_back({ hoursRequired(i, c), i });
}
sort(dis.begin(), dis.end());
num = 1;
subtree[0].push_back(dis[0]);
for (i = 1; i < dis.size(); i++) {
ll j;
for (j = 0; j < num; j++) {
if (j == 2) break;
if (hoursRequired(dis[i].second, subtree[j][0].second) != dis[i].first + subtree[j][0].first) break;
}
if (j == num) num++;
subtree[j].push_back(dis[i]);
}
vector<ll> ans;
assert(num >= 2);
if (num == 2) {
ll r = N;
ll a;
if (subtree[0].size() < subtree[1].size()) a = 1;
else a = 0;
while (r != 1) {
ans.push_back(e(subtree[a]).second);
subtree[a].pop_back();
a = !a;
r--;
}
ans.push_back(c);
}
else {
ll chk = 0;
ll r = N;
ll a;
vector<ll> asdf(N);
if (e(subtree[0]).first > e(subtree[1]).first) swap(subtree[0], subtree[1]);
if (e(subtree[1]).first > e(subtree[2]).first) swap(subtree[1], subtree[2]);
if (e(subtree[0]).first == e(subtree[1]).first && subtree[0].size() > subtree[1].size()) swap(subtree[0], subtree[1]);
if (e(subtree[1]).first == e(subtree[2]).first && subtree[1].size() > subtree[2].size()) swap(subtree[1], subtree[2]);
for (i = 0; i < 3; i++) {
for (auto x : subtree[i]) {
assert(!asdf[x.second]);
asdf[x.second]++;
}
}
for (i = 0; i < N; i++) {
assert(asdf[i] <= 1);
}
a = 2;
ll abc=c;
ll memo=-1;
assert((2*max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) <= (N)));
while (r != 1) {
ll b, c;
b = a + 1;
c = a + 2;
b %= 3;
c %= 3;
ll loc = subtree[a][subtree[a].size() - 1].second;
//assert(asdf[loc] == a);
ans.push_back(loc);
subtree[a].pop_back();
if (chk||2*max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= (r)-2) {
chk = 1;
ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() });
ll na=a;
if (a!=0&&mx == subtree[0].size()) na = 0;
if (a!=1&&mx == subtree[1].size()) na = 1;
if (a!=2&&mx == subtree[2].size()) na = 2;
if(memo==-1) memo=na;
if (memo == a) {
if(subtree[b].empty()&&subtree[c].empty()) {
while(1);
ans.push_back(abc);
ans.push_back(subtree[a][0].second);
return ans;
}
else if (e(subtree[b]).first < e(subtree[c]).first) a = c;
else if (e(subtree[b]).first == e(subtree[c]).first && (subtree[b].size() < subtree[c].size())) a = c;
else a = b;
}
else a = memo;
}
else {
if (e(subtree[b]).first < e(subtree[c]).first) a = c;
else if (e(subtree[b]).first == e(subtree[c]).first && (subtree[b].size() < subtree[c].size())) a = c;
else a = b;
}
r--;
}
for (i = 0; i < ans.size(); i++) assert(ans[i] != c);
ans.push_back(c);
}
vector<ll> asdfsdf(N);
for (i = 0; i < N; i++) asdfsdf[ans[i]] = 1;
for (i = 0; i < N; i++) assert(asdfsdf[i]);
return ans;
}