| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1064124 | DorostWef | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ask are_connected
std::vector<int> longest_trip(int N, int D) {
int n = N;
vector <int> A = {0}, B;
for (int i = 1; i < n; i++) {
if (B.empty()) {
bool f = ask ({A.back()}, {i});
if (f)
A.push_back(i);
else {
B.push_back(i);
}
} else {
if (ask ({A.back()}, {B[0]})) {
for (int x : B)
A.push_back(x);
B.clear();
i--;
} else if (ask ({A.back()}, {i})) {
A.push_back(i);
} else {
B.push_back(i);
}
}
}/*
cout << "A : ";
for (int x : A)
cout << x << ' ';
cout << '\n';
cout << "B : ";
for (int y : B)
cout << y << ' ';
cout << '\n';*/
if (B.empty()) {
assert (A.size() == n);
return A;
}
if (!ask (A, B)) {
if (A.size() >= B.size()) {
assert (A.size() >= (n + 1) / 2);
return A;
}
assert (B.size() >= (n + 1) / 2);
return B;
}
if (ask ({A[0]}, {B[0]})) {
reverse (A.begin(), A.end());
for (int x : B) {
A.push_back(x);
}
assert (A.size() == n);
return A;
} else {
bool f;
if (A.size() >= 2) {
f = ask ({A[0]}, {A.back()});
if (!f) {
for (int x : B) {
A.push_back(x);
}
assert (A.size() == n);
return A;
}
}
if (B.size() >= 2) {
f = ask ({B[0]}, {B.back()});
if (!f) {
for (int x : A) {
B.push_back(x);
}
assert (B.size() == n);
return B;
}
}
}
int l = -1, r = (int)A.size() - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
vector <int> C;
for (int i = 0; i <= mid; i++) {
C.push_back(A[i]);
}
if (ask (C, B)) {
r = mid;
} else {
l = mid;
}
}
vector <int> wef = {A[r]};
int ww1 = r;
l = -1, r = (int)B.size() - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
vector <int> C;
for (int i = 0; i <= mid; i++) {
C.push_back(B[i]);
}
if (ask (C, wef)) {
r = mid;
} else {
l = mid;
}
}
int ww2 = r;
vector <int> ans;
for (int i = ww1 + 1; i < (int)A.size(); i++) {
ans.push_back(A[i]);
}
for (int i = 0; i <= ww1; i++) {
ans.push_back(A[i]);
}
for (int i = ww2; i < (int)B.size(); i++) {
ans.push_back(B[i]);
}
for (int i = 0; i < ww2; i++) {
ans.push_back(B[i]);
}
assert (ask ({A[ww1]}, {B[ww2]}));
assert (ask ({A[0]}, {A.back()) || (int)A.size() == 1);
assert (ask ({B[0]}, {B.back()) || (int)B.size() == 1);
assert (ans.size() == n);
for (int i = 0; i < n - 1; i++) {
// assert (ask ({ans[i]}, {ans[i + 1]}));
}
return ans;
}