제출 #1137173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137173		shjeong	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	6 ms	416 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;
    deque<int> L = {0};
    set<int> not_in_l;
    ll l = 0, r = n;
    while(l+1 < r){
        ll mid = l+r>>1;
        vector<int> tmp;
        for(int i = 1 ; i <= mid ; i++)tmp.push_back(i);
        if(ask({0},tmp))r = mid;
        else l = mid;
    }
    if(r==n){ for(int i = 1 ; i < n ; i++)ret.push_back(i); return ret; }
    L.push_back(r);
    vector<int> v;
    for(int i = 1 ; i < n ; i++)if(i!=r)not_in_l.insert(i), v.push_back(i);
    for(auto i : v){
        if(!ask({L[0],L.back()}, {i}))continue;
        not_in_l.erase(i);
        if(ask({L[0]}, {i}))L.push_front(i);
        else L.push_back(i);
    }
    if(!sz(not_in_l)){for(auto i : L)ret.push_back(i); return ret;}
    v.clear(); for(auto i : not_in_l)v.push_back(i);
    l = -1, r = sz(L);
    while(l+1 < r){
        ll mid = l+r>>1;
        vector<int> tmp;
        for(int i = 0 ; i <= mid ; i++)tmp.push_back(L[i]);
        if(ask(v,tmp))r = mid;
        else l = mid;
    }
    if(r == sz(L)){    //컴포넌트 분리됨
        if(sz(v) < sz(L)){for(auto i : L)ret.push_back(i); return ret;}
        return v;   //v는 clique
    }
    else{
        ll idx = r;
        l = -1, r = sz(v);
        while(l+1 < r){
            ll mid = l+r>>1;
            vector<int> tmp;
            for(int i = 0 ; i <= mid ; i++)tmp.push_back(v[i]);
            if(ask({L[idx]},tmp))r = mid;
            else l = mid;
        }
        ll idx2 = r;
        if(idx==0){   //둘이 합침
            for(int i = (idx2+1)%sz(v), j = 0 ; j < sz(v) ; j++, i = (i+1)%sz(v)){
                ret.push_back(v[i]);
            }
            for(auto i : L)ret.push_back(i);
            return ret;
        }
        //여기서 L[0]와 L.back()은 연결이 보장됨
        for(int i = idx+1, j = 0 ; j < sz(L) ; j++, i = (i+1)%sz(L)){
            ret.push_back(L[i]);
        }
        for(int i = idx2, j = 0 ; j < sz(v) ; j++, i = (i+1)%sz(v)){
            ret.push_back(v[i]);
        }
        return ret;
    }
}

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