Submission #1137212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137212		shjeong	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	5 ms	428 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;
    for(int i = 1 ; i < n ; i++){
        if(ask({i}, {L1.back()}))L1.push_back(i);
        else{
            if(!sz(L2)){
                L2.push_back(i);
            }
            else{
                if(ask({i}, {L2.back()}))L2.push_back(i);
                else{
                    for(int j = sz(L2)-1 ; j >= 0 ; j--)L1.push_back(L2[j]);
                    L2 = {i};
                }
            }
        }
    }
    if(sz(L1)==n)return L1;
    if(sz(L2)==n)return L2;
    if(!ask(L1,L2))return (sz(L1) >= sz(L2) ? L1 : L2);
    if(ask({L1[0]}, {L2[0]})){
        for(int i = sz(L1)-1 ; i >= 0 ; i--)ret.push_back(L1[i]);
        for(auto i : L2)ret.push_back(i);
        return ret;
    }
    if(ask({L1[0]}, {L2.back()})){
        for(auto i : L2)ret.push_back(i);
        for(auto i : L1)ret.push_back(i);
        return ret;
    }
    if(ask({L1.back()}, {L2[0]})){
        for(auto i : L1)ret.push_back(i);
        for(auto i : L2)ret.push_back(i);
        return ret;
    }
    if(ask({L1.back()}, {L2.back()})){
        for(auto i : L1)ret.push_back(i);
        for(int i = sz(L2)-1 ; i >= 0 ; i--)ret.push_back(L2[i]);
        return ret;
    }
    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, 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