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 "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef int un;
typedef vector<un> vuc;
typedef deque<un> duc;
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define ALL(x) (x).begin(), (x).end()
#define vec vector
#define DEB(x) cerr << #x << " = " << x << endl;
un bs(un from, vuc field){
un L = 0;
un R = field.size();
while (R-L > 1)
{
un M = (L+R)/2;
if (are_connected({from}, vuc(field.begin() + L, field.begin()+M))){
R = M;
}
else{
L = M;
}
}
return field[L];
}
std::vector<int> longest_trip(int N, int D)
{
if (D == 3){
vuc ret(N);
iota(ALL(ret), 0);
return ret;
}
if (D == 2){
duc ret;
if (not are_connected({0}, {1})){
ret = {0, 2, 1};
}
else if (not are_connected({1}, {2})){
ret = {1, 0, 2};
}
else {
ret = {0, 1, 2};
}
REP(i, 3, N){
if (are_connected({ret.back()}, {i})){
ret.push_back(i);
}
else{
ret.push_front(i);
}
}
return vuc(ALL(ret));
}
if (D == 1){
vuc ret = {0};
vec<bool> was_used(N, false);
was_used[0] = true;
while (true)
{
vuc not_used = {};
REP(i, 0, N){
if (not was_used[i]){
not_used.push_back(i);
}
}
if (not are_connected(not_used, {ret[ret.size()-1]})){
if (ret.size() > not_used.size()){
return ret;
}
else{
return not_used;
}
}
un now = bs(ret[ret.size()-1], not_used);
ret.push_back(now);
was_used[now] = true;
}
return ret;
}
}
Compilation message (stderr)
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
99 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |