Submission #1233287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233287		Sir_Ahmed_Imran	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	6 ms	420 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int n;

vector<int> get(vector<int> & v, int x){
    vector<int> ans;
    for(int i = 0; i < x; i++)
        ans.append(v[i]);
    return ans;
}

vector<int> solve3(){
    vector<int> v;
    for(int i = 0; i < n; i++)
        v.append(i);
    return v;
}

vector<int> solve2(){
    deque<int> Q;
    Q.append(0);
    if(are_connected({0}, {1})){
        Q.append(1);
        if(are_connected({1}, {2}))
            Q.append(2);
        else Q.push_front(2);
    }
    else
        Q.append(2), Q.append(1);
    for(int i = 3; i < n; i++){
        if(are_connected({Q.back()}, {i}))
            Q.append(i);
        else Q.push_front(i);
    }
    vector<int> ans;
    while(!Q.empty()){
        ans.append(Q.front());
        Q.pop_front();
    }
    return ans;
}

vector<int> solve1(){
    int l, r;
    deque<int> d, q, t;
    d.append(0);
    vector<int> x, y, ans;
    for(int i = 1; i < n; i++){
        if(are_connected({d.back()}, {i})){
            d.append(i);
            if(!q.empty() && are_connected({i}, {q.back()})){
                while(!q.empty()){
                    d.append(q.back());
                    q.pop_back();
                }
            }
        }
        else q.append(i);
    }
    if(d.size() < q.size()) swap(d, q);
    t = d;
    while(!t.empty()){
        x.append(t.front());
        t.pop_front();
    }
    t = q;
    while(!t.empty()){
        y.append(t.front());
        t.pop_front();
    }
    if(y.empty() || !are_connected(x, y))
        return x;
    if(!are_connected({x[0]}, {x.back()})){
        if(are_connected({x[0]}, {y[0]}))
            reverse(all(x));
        for(auto & i : x)
            ans.append(i);
        for(auto & i : y)
            ans.append(i);
        return ans;
    }
    if(y.size() > 1 && !are_connected({y[0]}, {y.back()})){
        if(are_connected({y[0]}, {x[0]}))
            reverse(all(y));
        for(auto & i : y)
            ans.append(i);
        for(auto & i : x)
            ans.append(i);
        return ans;
    }
    l = r = 0;
    for(int i = 128; i > 0; i /= 2)
        if(l + i < x.size() && !are_connected(get(x, l + i), y))
            l += i;
    for(int i = 128; i > 0; i /= 2)
        if(r + i < y.size() && !are_connected({x[l]}, get(y, r + i)))
            r += i;
    for(int i = l + 1; i < x.size(); i++)
        ans.append(x[i]);
    for(int i = 0; i <= l; i++)
        ans.append(x[i]);
    for(int i = r; i < y.size(); i++)
        ans.append(y[i]);
    for(int i = 0; i < r; i++)
        ans.append(y[i]);
    return ans;
}

vector<int> longest_trip(int N, int D){
    n = N;
    if(D == 3)
        return solve3();
    if(D == 2)
        return solve2();
    return solve1();
}

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