| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 935223 | MinaRagy06 | 즐거운 행로 (APIO20_fun) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "fun.h"
using namespace std;
#define ll long long
vector<int> ans;
set<int> rem;
int n;
void solve(int i) {
if (rem.find(i) == rem.end()) {
return;
}
if ((i << 1) > n) {
ans.push_back(i);
rem.erase(ans.back());
return;
}
rem.erase(i);
vector<int> v[2];
for (auto j : rem) {
if (j == i) continue;
int diff = __lg(j) - __lg(i << 1);
v[(j >> diff) != (i << 1)].push_back(j);
}
int cur = 0;
while (v[1].size()) {
ans.push_back(v[cur].back());
rem.erase(ans.back());
v[cur].pop_back();
cur ^= 1;
}
solve(i << 1);
ans.push_back(i);
}
bool check(const std::vector<int>& fun_tour) {
if (static_cast<int>(fun_tour.size()) != n) {
return 0;
}
std::vector<bool> visited_attractions(N, false);
for (int i = 0; i < n; ++i) {
if (fun_tour[i] < 0 || fun_tour[i] >= n) {
return 0;
}
if (visited_attractions[fun_tour[i]]) {
return 0;
}
visited_attractions[fun_tour[i]] = true;
}
int last_travel_time = hoursRequired(fun_tour[0], fun_tour[1]);
for (int i = 2; i < n; ++i) {
int travel_time = hoursRequired(fun_tour[i - 1], fun_tour[i]);
if (travel_time > last_travel_time) {
return 0;
}
last_travel_time = travel_time;
}
return 1;
}
vector<int> solve() {
int dist[n][n]{};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = hoursRequired(i, j);
}
}
int u = 0;
array<int, 2> mx = {-1, -1};
for (int i = 0; i < n; i++) {
mx = max(mx, {dist[u][i], i});
}
u = mx[1];
vector<int> ans, v;
for (int i = 0; i < n; i++) {
if (i == u) continue;
v.push_back(i);
}
ans.push_back(u);
while (v.size()) {
mx = {-1, -1};
for (auto i : v) {
mx = max(mx, {dist[u][i], i});
}
u = mx[1];
ans.push_back(u);
vector<int> newv;
for (auto i : v) {
if (i == u) continue;
newv.push_back(i);
}
v = newv;
}
return ans;
}
vector<int> createFunTour(int _n, int q) {
n = _n;
N = n;
if (n <= 500) {
return solve();
}
for (int i = 1; i <= n; i++) {
rem.insert(i);
}
solve(1);
for (auto &i : ans) i--;
if (!check(ans)) {
return solve();
}
return ans;
}