| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 839861 | tamionv | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "longesttrip.h"
#include <iostream>
#include <random>
#include <utility>
using namespace std;
mt19937 mt(123);
bool my_are_connected(vector<int> a, vector<int> b) {
a.erase(unique(begin(a), end(a)), end(a));
b.erase(unique(begin(b), end(b)), end(b));
return are_connected(a, b);
}
pair<int, int> cbin(vector<int> as, vector<int> bs) {
shuffle(begin(as), end(as), mt);
shuffle(begin(bs), end(bs), mt);
bool swp = false;
if (as.size() > bs.size()) {
swap(as, bs);
swp = true;
}
pair<int, int> ret;
if (bs.size() == 1)
ret = make_pair(as[0], bs[0]);
else {
vector<int> xs(begin(bs), begin(bs) + bs.size() / 2), ys(begin(bs) + bs.size() / 2, end(bs));
if (my_are_connected(as, xs))
ret = cbin(as, xs);
else
ret = cbin(as, ys);
}
if (swp) swap(ret.first, ret.second);
return ret;
}
std::vector<int> longest_trip(int N, int D) {
mt = mt19937(123 + N + D);
vector<int> perm(N);
iota(begin(perm), end(perm), 0);
shuffle(begin(perm), end(perm), mt);
vector<int> xs = {}, ys = {};
for (auto x : perm) {
if (xs.empty())
xs.push_back(x);
else if (ys.empty()) {
if (my_are_connected({x}, {xs.back()}))
xs.push_back(x);
else
ys.push_back(x);
} else {
if (bernoulli_distribution(0.5)(mt)) {
if (!my_are_connected({x}, {xs.back()}))
ys.push_back(x);
else if (!my_are_connected({x}, {ys.back()}))
xs.push_back(x);
else {
xs.push_back(x);
xs.insert(end(xs), begin(ys), end(ys));
ys = {};
}
} else {
if (!my_are_connected({x}, {ys.back()}))
xs.push_back(x);
else if (!my_are_connected({x}, {xs.back()}))
ys.push_back(x);
else {
xs.push_back(x);
xs.insert(end(xs), begin(ys), end(ys));
ys = {};
}
}
}
}
vector<int> ret = {};
if (ys.empty())
ret = xs;
else {
if (!my_are_connected(xs, ys))
ret = (xs.size() < ys.size() ? ys : xs);
else if (my_are_connected({xs.front(), xs.back()}, {ys.front(), ys.back()})) {
auto [x, y] = cbin({xs.front(), xs.back()}, {ys.front(), ys.back()});
if (xs.back() != x) reverse(begin(xs), end(xs));
if (ys.front() != y) reverse(begin(ys), end(ys));
xs.insert(end(xs), begin(ys), end(ys));
ret = xs;
} else {
auto [x, y] = cbin(xs, ys);
rotate(begin(xs), find(begin(xs), end(xs), x), end(xs));
rotate(begin(ys), find(begin(ys), end(ys), y), end(ys));
reverse(begin(xs), end(xs));
xs.insert(end(xs), begin(ys), end(ys));
ret = xs;
}
}
return ret;
}