Submission #1242041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242041		a4n_	Longest Trip (IOI23_longesttrip)	C++20	70 / 100	12 ms	436 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<vector<int>, vector<int>> pvv;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n;

pvv merge3(vector<int> v1, vector<int> v2, vector<int> v3) {
    if(are_connected({v1[0]}, {v2[0]}) == 1) {
        reverse(all(v1));
        for(auto it : v2) v1.pb(it);
        return {v1, v3};
    }
    if(are_connected({v1[0]}, {v3[0]}) == 1) {
        reverse(all(v1));
        for(auto it : v3) v1.pb(it);
        return {v1, v2};
    } 

    reverse(all(v2));
    for(auto it : v3) v2.pb(it);
    return {v1, v2};
}

pvv merge2(vector<int> v1, vector<int> v2) {
    if(size(v1) > 1 && are_connected({v1[0]}, {v1.back()}) == 0) {
        if(are_connected({v1[0]}, {v2[0]}) == 1) {
            reverse(all(v1));
        }

        for(auto it : v2) v1.pb(it);
        return {v1, {}};
    }

    if(size(v2) > 1 && are_connected({v2[0]}, {v2.back()}) == 0) {
        if(are_connected({v2[0]}, {v1[0]}) == 1) {
            reverse(all(v2));
        }

        for(auto it : v1) v2.pb(it);
        return {v2, {}};
    }

    if(size(v1) > size(v2)) swap(v1, v2);

    vector<int> tmp = v1, tmp2 = v2;

    if(are_connected(tmp, tmp2) == 0) {
        return {v1, v2};
    }

    while(size(tmp) > 1) {
        vector<int> tt;
        for(int i=size(tmp)/2; i<size(tmp); i++) {
            tt.pb(tmp[i]);
        }
        if(are_connected(tt, tmp2) == 1) {
            tmp = tt;
        } else {
            int x = size(tmp) / 2;
            while(size(tmp) > x) tmp.pop_back();
        }
    }
    while(size(tmp2) > 1) {
        vector<int> tt;
        for(int i=size(tmp2)/2; i<size(tmp2); i++) {
            tt.pb(tmp2[i]);
        }
        if(are_connected(tt, tmp) == 1) {
            tmp2 = tt;
        } else {
            int x = size(tmp2) / 2;
            while(size(tmp2) > x) tmp2.pop_back();
        }
    }

    int id = 0, id2 = 0;
    for(int i=0; i<size(v1); i++) {
        if(v1[i] == tmp[0]) id = i;
    }

    for(int i=0; i<size(v2); i++) {
        if(v2[i] == tmp2[0]) id2 = i;
    }

    vector<int> res;
    for(int i=id+1; i<size(v1); i++) res.pb(v1[i]);
    for(int i=0; i<=id; i++) res.pb(v1[i]);
    for(int i=id2; i<size(v2); i++) res.pb(v2[i]);
    for(int i=0; i<id2; i++) res.pb(v2[i]);

    return {res, {}};
}

pvv divide(int l, int r) {
    if(l == r) {
        return {{l}, {}};
    }
    if(l == r - 1) {
        if(are_connected({l}, {r}) == 1) {
            return {{l, r}, {}};
        }
        return {{l}, {r}};
    }

    int mid = (l + r) / 2;
    pvv r1 = divide(l, mid), r2 = divide(mid+1, r);

    vector<vector<int>> paths;
    paths.pb(r1.F);
    paths.pb(r2.F);

    if(size(r1.S) > 0) paths.pb(r1.S);
    if(size(r2.S) > 0) paths.pb(r2.S);

    while(size(paths) >= 3) {
        int x = size(paths) - 1;
        pvv tmp = merge3(paths[x], paths[x-1], paths[x-2]);
        paths.pop_back();paths.pop_back();paths.pop_back();
        paths.pb(tmp.F);
        paths.pb(tmp.S);
    }

    pvv tmp = merge2(paths[0], paths[1]);
    return tmp;
}

vector<int> longest_trip(int _N, int _D) {
    n = _N;

    pvv ans = divide(0, n-1);

    if(size(ans.F) > size(ans.S)) {
        // for(auto it : ans.F) {fuck(it);}
        // for(auto it : ans.S) {fuck(it);}
        return ans.F;
    }
    // for(auto it : ans.F) {fuck(it);}
    // for(auto it : ans.S) {fuck(it);}

    return ans.S;
}

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