Submission #1081564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081564		idas	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	13 ms	700 KiB

longesttrip

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

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=300;
int n, d;

map<pii, bool> mp;
bool con(int a, int b) {
    if(mp.count({a,b})) return mp[{a,b}];
    if(mp.count({b,a})) return mp[{b,a}];
    return mp[{a,b}]=are_connected({a},{b});
}

void mrg(vi &a, vi &b) {
    while(!b.empty()) {
        a.pb(b.back());
        b.pop_back();
    }
}

void dbg(vi &a, vi&b) {
    cout << "a: "; for(auto it : a) cout << it << " "; cout << endl;
    cout << "b: "; for(auto it : b) cout << it << " "; cout << endl;
}

std::vector<int> longest_trip(int N, int D) {
    mp.clear();
    n=N; d=D;
    vi in; FOR(i, 0, n) in.pb(i);
    shuffle(in.begin(), in.end(), rng);

    bool conn=true;
    vi a, b; a.pb(in[0]);
    FOR(i, 1, n) {
        if(b.empty()) {
            b.pb(in[i]);
            continue;
        }

        if(con(a.back(), in[i])) a.pb(in[i]), conn=true;
        else if(!conn) b.pb(in[i]);
        else if(con(b.back(), in[i])) b.pb(in[i]), conn=false;
        else mrg(a, b), b.pb(in[i]), conn=true;
    }

    if(b.empty()) return a;

    if(con(a[0], b[0])) {
        reverse(a.begin(), a.end());
        for(auto it : b) a.pb(it);
        return a;
    }
    if(con(a[0], b.back())) {
        for(auto it : a) b.pb(it);
        return b;
    }
    if(con(a.back(), b[0])) {
        for(auto it : b) a.pb(it);
        return a;
    }
    if(con(a.back(), b.back())) {
        while(!b.empty()) a.pb(b.back()), b.pop_back();
        return a;
    }

    if(sz(b)>sz(a)) swap(a, b);
    if(!are_connected(a, b)) return a;

    int l=0, r=sz(b)-1;
    while(l<r) {
        int m=(l+r)/2;
        vi tmp; FOR(i, l, m+1) tmp.pb(b[i]);
        if(are_connected(a, tmp)) r=m;
        else l=m+1;
    }
    assert(are_connected({b[l]}, a));
    int bin=l;

    l=0; r=sz(a)-1;
    while(l<r) {
        int m=(l+r)/2;
        vi tmp; FOR(i, l, m+1) tmp.pb(a[i]);
        if(are_connected({b[bin]}, tmp)) r=m;
        else l=m+1;
    }
    int ain=l;


    // cout << ":\n";
    // for(auto it : a) cout << it << " "; cout << endl;
    // for(auto it : b) cout << it << " ";
    // cout << "ins: " << ain << " " << bin << endl;

    vi ans;
    FOR(i, 1, sz(a)+1) {
        int id=(ain+i)%sz(a);
        ans.pb(a[id]);
    }
    FOR(i, 0, sz(b)) {
        int id=(bin+i)%sz(b);
        ans.pb(b[id]);
    }
    return ans;
}
/*
1
5 1
1
1 1
0 0 1
0 0 0 1
*/

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