Submission #1137202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137202		shjeong	Longest Trip (IOI23_longesttrip)	C++20	70 / 100	29 ms	476 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> L = {0};
    set<int> not_in_l;
    for(int i = 1 ; i < n ; i++)not_in_l.insert(i);
    while(sz(not_in_l)){
        vector<int> v;
        for(auto i : not_in_l)v.push_back(i);
        ll l = -1, r = sz(v);   //처음으로 connected 되는 위치가 r에 저장됨
        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.back()}, tmp))r = mid;
            else l = mid;
        }
        if(r == sz(v))break;
        L.push_back(v[r]); not_in_l.erase(v[r]);
    }
    if(!sz(not_in_l))return L;
    vector<int> v;
    for(auto i : not_in_l)v.push_back(i);
    ll 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))return L;
        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: 25 / 25
• Subtask 4: 30 / 60