제출 #1242193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242193		MrAndria	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	8 ms	424 KiB

longesttrip

// #include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

#include "longesttrip.h"

// #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;
// }
std::vector<int> longest_trip(int N, int D){
    vector <int> v5;
    for(int i=0;i<N;i++){
        v5.pb(i);
        
    }
    std::random_device rd;
    std::mt19937 g(rd());
 
    std::shuffle(v5.begin(), v5.end(), g);
    vector <int> v1,v2;
    v1.pb(v5[0]);
    v2.pb(v5[1]);
    for(int i=2;i<N;i++){
        if(are_connected({v1.back()},{v5[i]})){
            v1.pb(v5[i]);
            continue;
        }
        if(are_connected({v2.back()},{v5[i]})){
            v2.pb(v5[i]);
            continue;
        }
        reverse(v2.begin(),v2.end());
        for(auto u:v2){
            v1.pb(u);
        }
        v2.clear();
        v2.pb(v5[i]);
    }
    if(v1.size()!=1 and v2.size()!=1){
        if(are_connected({v1[0],v1.back()},{v2[0],v2.back()})){
            if(are_connected({v1.back()},{v2[0]})){
                for(auto u:v2){
                    v1.pb(u);

                }
                return v1;
            }else if(are_connected({v1.back()},{v2.back()})){
                reverse(v2.begin(),v2.end());
                for(auto u:v2){
                    v1.pb(u);

                }
                return v1;
            }else if(are_connected({v1[0]},{v2.back()})){
                for(auto u:v1){
                    v2.pb(u);

                }
                return v2;
            }else{
                reverse(v1.begin(),v1.end());
                for(auto u:v1){
                    v2.pb(u);

                }
                return v2;
            }

        }
    }else{
        if(v2.size()<=v1.size()){
            swap(v1,v2);

        }
        if(are_connected({v1.back()},{v2[0],v2.back()})){
            if(are_connected({v1.back()},{v2[0]})){
                for(auto u:v2){
                    v1.pb(u);
                }
                return v1;
            }else{
                v2.pb(v1[0]);
                return v2;
            }
        }
        // return {-1,-1,-1,-1};
    }
    int l,r,ans,mid,ans1;
    l=0;
    r=v1.size()-1;
    ans=-1;
    while(l<=r){
        mid=(l+r)/2;
        vector <int> v3;
        for(int i=0;i<=mid;i++){
            v3.pb(v1[i]);
        }
        if(are_connected(v3,v2)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }

    }
    if(ans==-1){
        if(v1.size()>=v2.size()){
            return v1;
        }else{
            return v2;
        }
    }
    l=0;
    r=v2.size()-1;
    ans1=-1;
    while(l<=r){
        mid=(l+r)/2;
        vector <int> v3;
        for(int i=0;i<=mid;i++){
            v3.pb(v2[i]);
        }
        if(are_connected({v1[ans]},v3)){
            ans1=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }

    }
    if(ans1<0){
        assert(0);
    }
    vector <int> v;
    for(int i=ans+1;i<v1.size();i++){
        v.pb(v1[i]);
    }
    for(int i=0;i<=ans;i++){
        v.pb(v1[i]);

    }
    for(int i=ans1;i<v2.size();i++){
        v.pb(v2[i]);
    }
    for(int i=0;i<ans1;i++){
        v.pb(v2[i]);
    }
    return v;

}
// 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);
//         // if(l!=10){
//         //     // cout<<"YESSSSSSSS"<<endl;
//         // }
//         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;
// }

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