Submission #1154347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154347		modwwe	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	6 ms	436 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
/*#include <cassert>
#include <cstdio>
#include <string>
#include <vector>*/
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;
}*/
#define pb push_back
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int t;
int el = 19;
vector<int> v,v2;
vector<int> cvc(vector<int>&v,int l,int r)
{
    vector<int> haha(v.begin()+l,v.begin()+r+1);
    return haha;
}
vector<int> longest_trip(int N,int D)
{
    n=N;
    m=D;
    v.clear();
    v2.clear();
    v.pb(0);
    v2.pb(1);
    bool de=0;
    for(int i=2; i<n; i++)
    {
        if(are_connected({v.back()}, {i}))
        {
            v.pb(i),de=0;
        }
        else if(de||are_connected({v2.back()}, {i}))
        {
            v2.pb(i);
            de=1;
        }
        else
        {
            reverse(v2.begin(),v2.end());
            for(auto x:v2)v.pb(x);
            v2.clear();
            v2.pb(i);
            de=0;
        }
    }
    if(are_connected(v,v2))
    {
        l=1;
        r=v.size()-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            vector<int> haha=cvc(v,mid,v.size()-1);
            if(are_connected(v2,haha))l=mid+1;
            else r=mid-1;
        }
       // debug
        s2=l-1;
        l=1;
        r=v2.size()-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            vector<int> haha=cvc(v2,mid,v2.size()-1);
            if(are_connected({v[s2]},haha))l=mid+1;
            else r=mid-1;
        }
        s3=l-1;
        if(are_connected({v[0]}, {v2[0]}))
        {
            reverse(v.begin(),v.end());
            for(auto x:v2)v.pb(x);
            return v;
        }
        if(are_connected({v[0]}, {v2.back()}))
        {
            reverse(v.begin(),v.end());
            reverse(v2.begin(),v2.end());
            for(auto x:v2)v.pb(x);
            return v;
        }
        if(are_connected({v.back()}, {v2.back()}))
        {
            ///reverse(v.begin(),v.end());
            reverse(v2.begin(),v2.end());
            for(auto x:v2)v.pb(x);
            return v;
        }
        if(are_connected({v.back()}, {v2[0]}))
        {
            ///reverse(v.begin(),v.end());
            ///  reverse(v2.begin(),v2.end());
            for(auto x:v2)v.pb(x);
            return v;
        }
        if(are_connected({v[s2]}, {v2[0]}))
        {
            vector<int> ans;
            for(int i=s2+1; i<v.size(); i++)ans.pb(v[i]);
            for(int i=0; i<=s2; i++)ans.pb(v[i]);
            for(auto x:v2)ans.pb(x);
            return ans;
        }
        if(are_connected({v[0]}, {v2[s3]}))
        {
            reverse(v.begin(),v.end());
            for(int i=s3; i<v2.size(); i++)v.pb(v2[i]);
            for(int i=0; i<s3; i++)v.pb(v2[i]);
            return v;
        }
        vector<int> ans;
        for(int i=s2+1; i<v.size(); i++)ans.pb(v[i]);
        for(int i=0; i<=s2; i++)ans.pb(v[i]);
        for(int i=s3; i<v2.size(); i++)ans.pb(v2[i]);
        for(int i=0; i<s3; i++)ans.pb(v2[i]);
        return ans;
    }
    else
    {
        if(v.size()>v2.size()) return v;
        return v2;
    }
}
/*
int main()
{
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    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]);
        if(i!=l-1){
        s2=min(t[i],t[i+1]);
        s3=max(t[i],t[i+1]);
         if(U[s3][s2]!=1)assert(0);
        }
        }
        printf("\n");
        printf("%d\n", call_counter);

        maximumCalls = std::max(maximumCalls, call_counter);
        call_counter = 0;
    }
    printf("%d\n", maximumCalls);

    return 0;
}*/

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60