// by me
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
bool are_connected(std::vector<int> A, std::vector<int> B);
bool con(vector<int> a, vector<int> b){
return are_connected(a, b);
}
std::vector<int> longest_trip(int N, int D)
{
vector<int> v1 = {0}, v2 = {1};
for(int i = 2; i < N; i++){
if(i == N - 1){
// con?(a, b) -> mrg(a, b)
if(con({v1.back()}, {N - 1})){
v1.push_back(N - 1);
}
// con?(c, b) -> mrg(c, b)
else if(con({v2.back()}, {N - 1})){
v2.push_back(N - 1);
}
// mrg(a, c)
else{
for(int i = v2.size() - 1; i >= 0; i--){
v1.push_back(v2[i]);
}
v2 = {N - 1};
}
}
else{
// con?(a, b) -> mrg(a, b)
if(con({v1.back()}, {i})){
v1.push_back(i);
}
// con?(c, b) -> mrg(c, b)
else if(con({v2.back()}, {i})){
v2.push_back(i);
// con?(b, d) -> mrg(b, d) : mrg(a, d)
(con({i}, {i + 1}) ? v2 : v1).push_back(i + 1);
i++;
}
// con?(b, d) -> mrg(b, d), mrg(a, c)
if(con({i}, {i + 1})){
for(int j = v2.size() - 1; j >= 0; j--){
v1.push_back(v2[j]);
}
v2 = {i, i + 1};
i++;
}
// mrg(d, c), mrg(a, c);
else{
v2.push_back(i + 1);
for(int j = v2.size() - 1; j >= 0; j--){
v1.push_back(v2[j]);
}
v2 = {i};
i++;
}
}
}
// // !con?(v1, v2);
// if(!con(v1, v2)){
// return v1.size() > v2.size() ? v1 : v2;
// }
// con?(v1, v2)
if(con({v1.back()}, {v2.back()})){
for(int i = v2.size() - 1; i >= 0; i--){
v1.push_back(v2[i]);
}
return v1;
}
if(con({v1[0]}, {v2.back()})){
reverse(all(v1));
for(int i = v2.size() - 1; i >= 0; i--){
v1.push_back(v2[i]);
}
return v1;
}
if(con({v1.back()}, {v2[0]})){
for(int i = 0; i < v2.size(); i++){
v1.push_back(v2[i]);
}
return v1;
}
if(con({v1[0]}, {v2[0]})){
reverse(all(v1));
for(int i = 0; i < v2.size(); i++){
v1.push_back(v2[i]);
}
return v1;
}
vector<int> ans;
int l1 = 0, r1 = v1.size() - 1, k1 = 0;
while(l1 <= r1){
int mid = (l1 + r1) / 2;
vector<int> f;
for(int i = l1; i <= mid; i++){
f.push_back(v1[i]);
}
if(con(f, v2)){
r1 = mid - 1;
k1 = mid;
}
else{
l1 = mid + 1;
}
}
for(int i = 0; i < v1.size(); i++){
int j = (i + k1) % v1.size();
ans.push_back(v1[j]);
}
reverse(all(ans));
int l2 = 0, r2 = v2.size() - 1, k2 = 0;
while(l2 <= r2){
int mid = (l2 + r2) / 2;
vector<int> f;
for(int i = l2; i <= mid; i++){
f.push_back(v2[i]);
}
if(con(f, {v1[k1]})){
r2 = mid - 1;
k2 = mid;
}
else{
l2 = mid + 1;
}
}
for(int i = 0; i < v2.size(); i++){
int j = (i + k2) % v2.size();
ans.push_back(v2[j]);
}
return ans;
}
//
/*
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;
static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;
static inline void protocol_violation(std::string message)
{
printf("Protocol Violation: %s\n", message.c_str());
exit(0);
}
bool are_connected(std::vector<int> A, std::vector<int> B)
{
++call_counter;
++total_call_counter;
if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
{
protocol_violation("too many calls");
}
int nA = A.size(), nB = B.size();
landmark_counter += nA + nB;
if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
{
protocol_violation("too many elements");
}
if (nA == 0 || nB == 0)
{
protocol_violation("invalid array");
}
for (int i = 0; i < nA; ++i)
{
if (A[i] < 0 || N <= A[i])
{
protocol_violation("invalid array");
}
if (present[A[i]])
{
protocol_violation("invalid array");
}
present[A[i]] = true;
}
for (int i = 0; i < nA; ++i)
{
present[A[i]] = false;
}
for (int i = 0; i < nB; ++i)
{
if (B[i] < 0 || N <= B[i])
{
protocol_violation("invalid array");
}
if (present[B[i]])
{
protocol_violation("invalid array");
}
present[B[i]] = true;
}
for (int i = 0; i < nB; ++i)
{
present[B[i]] = false;
}
for (int i = 0; i < nA; ++i)
{
for (int j = 0; j < nB; ++j)
{
if (A[i] == B[j])
{
protocol_violation("non-disjoint arrays");
}
}
}
for (int i = 0; i < nA; ++i)
{
for (int j = 0; j < nB; ++j)
{
if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
{
return true;
}
}
}
return false;
}
int main()
{
assert(1 == scanf("%d", &C));
int maximumCalls = 0;
for (int c = 0; c < C; ++c)
{
call_counter = 0;
assert(2 == scanf("%d %d", &N, &D));
present.assign(N, false);
U.resize(N);
for (int i = 1; i < N; ++i)
{
U[i].resize(i);
for (int j = 0; j < i; ++j)
{
assert(1 == scanf("%d", &U[i][j]));
}
}
for (int i = 2; i < N; ++i)
{
for (int j = 1; j < i; ++j)
{
for (int k = 0; k < j; ++k)
{
if (U[i][j] + U[i][k] + U[j][k] < D)
{
printf("Insufficient Density\n");
exit(0);
}
}
}
}
std::vector<int> t = longest_trip(N, D);
int l = t.size();
printf("%d\n", l);
for (int i = 0; i < l; ++i)
{
printf(i == 0 ? "%d" : " %d", t[i]);
}
printf("\n");
printf("%d\n", call_counter);
maximumCalls = std::max(maximumCalls, call_counter);
call_counter = 0;
}
printf("%d\n", maximumCalls);
return 0;
}
//*/
// by me
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < v2.size(); i++){
| ~~^~~~~~~~~~~
longesttrip.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < v2.size(); i++){
| ~~^~~~~~~~~~~
longesttrip.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i = 0; i < v1.size(); i++){
| ~~^~~~~~~~~~~
longesttrip.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i = 0; i < v2.size(); i++){
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
