| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1145471 | AlgorithmWarrior | Longest Trip (IOI23_longesttrip) | C++20 | 0 ms | 0 KiB |
#include "longesttrip.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <deque>
#include <bits/stdc++.h>
using namespace std;
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;
}
vector<int>prefix(vector<int>v,int ind){
vector<int>pref;
int i;
for(i=0;i<=ind;++i)
pref.push_back(v[i]);
return pref;
}
vector<int>ocol(vector<int>v,int val){
int i;
int poz=0;
for(i=0;i<(int)v.size();++i)
if(v[i]==val)
poz=i;
vector<int>ans;
for(i=poz-1;i>=0;--i)
ans.push_back(v[i]);
for(i=v.size()-1;i>poz;--i)
ans.push_back(v[i]);
return ans;
}
std::vector<int> longest_trip(int N, int D){
if(D==3){
int i;
vector<int>path;
for(i=0;i<N;++i)
path.push_back(i);
return path;
}
else if(D==2){
int i;
deque<int>path;
int vec0;
if(are_connected({0},{1}))
vec0=1;
else
vec0=2;
path.push_back(0);
path.push_back(vec0);
for(i=1;i<N;++i)
if(i!=vec0){
if(are_connected({path.front()},{i}))
path.push_front(i);
else
path.push_back(i);
}
vector<int>ans;
for(auto el : path)
ans.push_back(el);
return ans;
}
else{
vector<int>unu,doi;
int i;
vector<int>perm;
for(i=0;i<N;++i)
perm.push_back(i);
srand(time(0));
for(i=1;i<N;++i){
int sch=rand()%(i+1);
swap(perm[i],perm[sch]);
}
unu.push_back(perm[0]);
int ifor;
for(ifor=1;ifor<N;++ifor){
i=perm[ifor];
if(doi.empty()){
if(are_connected({unu.back()},{i}))
unu.push_back(i);
else
doi.push_back(i);
}
else{
if(rand()%2==0)
swap(unu,doi);
if(!are_connected({unu.back()},{i}))
doi.push_back(i);
else{
if(!are_connected({doi.back()},{i}))
unu.push_back(i);
else{
unu.push_back(i);
reverse(doi.begin(),doi.end());
for(auto el : doi)
unu.push_back(el);
doi.clear();
}
}
}
}
if(doi.empty())
return unu;
if(!are_connected(unu,doi)){
if(unu.size()<doi.size())
swap(unu,doi);
return unu;
}
if(are_connected({unu.front()},{doi.front()})){
reverse(unu.begin(),unu.end());
for(auto el : doi)
unu.push_back(el);
return unu;
}
if(are_connected({unu.front()},{doi.back()})){
reverse(unu.begin(),unu.end());
reverse(doi.begin(),doi.end());
for(auto el : doi)
unu.push_back(el);
return unu;
}
if(are_connected({unu.back()},{doi.front()})){
for(auto el : doi)
unu.push_back(el);
return unu;
}
/// (]
int st=-1,dr=unu.size()-1;
while(dr-st>1){
int mij=(st+dr)/2;
if(are_connected(prefix(unu,mij),doi))
dr=mij;
else
st=mij;
}
vector<int>unu_nod;
unu_nod.push_back(unu[dr]);
st=-1,dr=doi.size()-1;
while(dr-st>1){
int mij=(st+dr)/2;
if(are_connected(prefix(doi,mij),unu_nod))
dr=mij;
else
st=mij;
}
vector<int>rasp;
vector<int>part;
part=ocol(unu,unu_nod[0]);
for(auto el : part)
rasp.push_back(el);
rasp.push_back(unu_nod[0]);
rasp.push_back(doi[dr]);
part=ocol(doi,doi[dr]);
for(auto el : part)
rasp.push_back(el);
return rasp;
}
}
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;
}