Submission #1202837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202837		PagodePaiva	Longest Trip (IOI23_longesttrip)	C++20	85 / 100	7 ms	456 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 260;

bool query(vector <int> a, vector <int> b){
    if(a == b)
        return true;
    return are_connected(a, b);
}

vector<int> longest_trip(int n, int D){
    queue <vector <int>> pq;
    for(int i = 0;i < n;i++){
        pq.push({i});
    }
    while(pq.size() > 2){
        vector <int> a = pq.front();
        pq.pop();
        vector <int> b = pq.front();
        pq.pop();
        vector <int> c = pq.front();
        pq.pop();
        if(query({a.back()}, {b.back(), c.back()})){
            if(!query({a.back()}, {b.back()})){
                swap(b, c);
            }
            reverse(b.begin(), b.end());
            for(auto x : b)
                a.push_back(x);
            pq.push(a);
            pq.push(c);
        }
        else{
            reverse(b.begin(), b.end());
            for(auto x : b)
                c.push_back(x);
            pq.push(a);
            pq.push(c);            
        }
    }
    vector <int> a = pq.front();
    pq.pop();
    vector <int> c = pq.front();
    pq.pop();
    if(!query(a, c)){
        if(a.size() < c.size())
            swap(a, c);
        return a;
    }
    if(!query({c[0]}, {c.back()}))
        swap(a, c);
    if(!query({a[0]}, {a.back()})){
        if(query({a[0]}, {c[0]})){
            reverse(a.begin(), a.end());
            for(auto x : c)
                a.push_back(x);
            return a;
        }
        else{
            for(auto x : c)
                a.push_back(x);
            return a;
        }
    }
    int l = 0, r = a.size();
    r--;
    while(l < r){
        int mid = (l+r)/2;
        vector <int> v;
        for(int i = l;i <= mid;i++){
            v.push_back(a[i]);
        }
        if(are_connected(v, c)){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    int x = a[l];
    l = 0;
    r = c.size();
    r--;
    while(l < r){
        int mid = (l+r)/2;
        vector <int> v;
        for(int i = l;i <= mid;i++){
            v.push_back(c[i]);
        }
        if(are_connected(v, {x})){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    int y = c[l];
    while(a.back() != x){
        int t = a[0];
        reverse(a.begin(), a.end());
        a.pop_back();
        reverse(a.begin(), a.end());
        a.push_back(t);
    }
    while(c.back() != y){
        int t = c[0];
        reverse(c.begin(), c.end());
        c.pop_back();
        reverse(c.begin(), c.end());
        c.push_back(t);
    }
    reverse(c.begin(), c.end());
    for(auto x : c)
        a.push_back(x);
    return a;
}

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