제출 #1137228

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

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
bool ask(vector<int> u, vector<int> v){
    return are_connected(u,v);
}
std::vector<int> longest_trip(int n, int D)
{
    //D=1
    vector<int> ret;
    vector<int> L1 = {0}, L2;
    if(ask({0},{1}))L1.push_back(1);
    else L2 = {1};
    for(int i = 2 ; i < n ; i+=2){
        if(i+1 == n){
            if(ask({L1.back()}, {i})){
                if(sz(L2) and ask({L2.back()}, {i})){
                    L1.push_back(i);
                    for(int j = sz(L2)-1 ; j >= 0 ; j--)L1.push_back(L2[j]);
                    L2.clear();
                }
                else L1.push_back(i);
            }
            else L2.push_back(i);
        }
        else{
            if(!sz(L2)){
                int x = i, y = i+1;
                bool xy = ask({x}, {y}), x1 = ask({x}, {L1.back()}), y1 = ask({y}, {L1.back()});
                if(xy){
                    if(x1)L1.push_back(x), L1.push_back(y);
                    else if(y1)L1.push_back(y), L1.push_back(x);
                    else L2 = {x,y};
                }
                else{
                    //x1 or y1
                    if(x1)L1.push_back(x), L2 = {y};
                    else L1.push_back(y), L2 = {x};
                }
            }
            else{
                int x = i, y = i+1;
                bool xy = ask({x}, {y});
                if(xy){
                    bool x1 = ask({x}, {L1.back()});
                    if(x1){
                        bool y2 = ask({y}, {L2.back()});
                        if(y2){
                            L1.push_back(x), L1.push_back(y);
                            for(int j = sz(L2)-1 ; j >= 0 ; j--)L1.push_back(L2[j]);
                            L2.clear();
                        }
                        else L1.push_back(x), L1.push_back(y);
                    }
                    else{
                        //x2 true
                        bool y1 = ask({y}, {L1.back()});
                        if(y1){
                            L1.push_back(y), L1.push_back(x);
                            for(int j = sz(L2)-1 ; j >= 0 ; j--)L1.push_back(L2[j]);
                            L2.clear();
                        }
                        else L2.push_back(x), L2.push_back(y);
                    }
                }
                else{
                    bool x1 = ask({x}, {L1.back()});
                    if(x1){
                        bool y2 = ask({y}, {L2.back()});
                        if(y2){
                            L1.push_back(x);
                            L2.push_back(y);
                        }
                        else{
                            L1.push_back(y);
                            L2.push_back(x);
                        }
                    }
                    else{
                        //x2, y1 true
                        L1.push_back(y);
                        L2.push_back(x);
                    }
                }
            }
        }
    }
    if(sz(L1)==n)return L1;
    if(sz(L2)==n)return L2;
    if(!ask(L1,L2))return (sz(L1) >= sz(L2) ? L1 : L2);
    assert(!ask({L1.back()},{L2.back()}));
    ll l = -1, r = sz(L2);
    while(l+1 < r){
        ll mid = l+r>>1;
        vector<int> tmp;
        for(int i = 0 ; i <= mid ; i++)tmp.push_back(L2[i]);
        if(ask(L1,tmp))r=mid;
        else l=mid;
    }
    ll idx2 = r;
    l = -1, r = sz(L1);
    while(l+1 < r){
        ll mid = l+r>>1;
        vector<int> tmp;
        for(int i = 0 ; i <= mid ; i++)tmp.push_back(L1[i]);
        if(ask({L2[idx2]}, tmp))r=mid;
        else l=mid;
    }
    ll idx = r;
    for(int i = (idx+1)%sz(L1), j = 0 ; j < sz(L1) ; j++, i = (i+1)%sz(L1))ret.push_back(L1[i]);
    for(int i = idx2, j = 0 ; j < sz(L2) ; j++, i = (i+1)%sz(L2))ret.push_back(L2[i]);
    return ret;
}

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