Submission #1168023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168023		Sang	Longest Trip (IOI23_longesttrip)	C++20	85 / 100	5 ms	420 KiB

longesttrip

#ifndef _Pbrngw_
#include "longesttrip.h"
#endif // _Pbrngw_
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

bool are_connected(vi A, vi B);

vector<int> longest_trip(int n, int D){
    if (D == 3){
        vi ans;
        FOR (i, 0, n - 1) ans.pb(i);
        return ans;
    }
    if (D == 2){
        deque<int> ans;
        ans.pb(0);
        vector<bool> marked(n, 0);
        marked[0] = 1;
        FOR (i, 1, n - 1){
            if (are_connected({0}, {i})){
                marked[i] = 1;
                ans.pb(i);
                break;
            }
        }
        FOR (i, 0, n - 1){
            if (marked[i]) continue;
            if (are_connected({ans.front()}, {i})){
                ans.push_front(i);
            } else ans.pb(i);
        }
        vi res;
        FOR (i, 0, n - 1) res.pb(ans[i]);
        assert(res.size() == n);
        return res;
    }
    vi A, B;
    A.pb(0);
    B.pb(1);
    FOR (i, 2, n - 1){
        if (are_connected({A.back()}, {i})){
            A.pb(i);
            continue;
        }
        if (are_connected({B.back()}, {i})){
            B.pb(i);
            continue;
        }
        reverse(ALL(B));
        for (int &x : B) A.pb(x);
        B.clear();
        B.pb(i);
    }
    if (!are_connected(A, B)){
        if (A.size() > B.size()) return A;
        return B;
    }

    if (are_connected({A.back()}, {B.back()})){
        reverse(ALL(B));
        for (int &x : B) A.pb(x);
        return A;
    }
    if (are_connected({A.back()}, {B.front()})){
        for (int &x : B) A.pb(x);
        return A;
    }
    if (are_connected({A.front()}, {B.back()})){
        for (int &x : A) B.pb(x);
        return B;
    }
    if (are_connected({A.front()}, {B.front()})){
        reverse(ALL(B));
        for (int &x : A) B.pb(x);
        return B;
    }
    int l = 0, r = (int)B.size() - 1, ans = -1;
    while (l <= r){
        int m = (l + r) / 2;
        vi vec;
        FOR (i, 0, m) vec.pb(B[i]);
        if (are_connected(A, vec)){
            ans = B[m];
            r = m - 1;
        } else l = m + 1;
    }
    assert(ans != -1);
    while (B.front() != ans){
        B.pb(B.front());
        B.erase(B.begin());
    }
    l = 0;
    r = (int)A.size() - 1;
    ans = -1;
    while (l <= r){
        int m = (l + r)/2;
        vi vec;
        FOR (i, 0, m) vec.pb(A[i]);
        if (are_connected(vec, {B.front()})){
            ans = A[m];
            r = m - 1;
        } else l = m + 1;
    }
    assert(ans != -1);
    while (A.front() != ans){
        A.pb(A.front());
        A.erase(A.begin());
    }
    reverse(ALL(B));
    for (int &x : A) B.pb(x);
    return B;
}

#ifdef _Pbrngw_

bool are_connected(vi A, vi B){
    cout << A[0] << ' ' << B[0] << endl;
    int x; cin >> x;
    return x;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    vi ans = longest_trip(5, 1);
    for (int &x : ans) cout << x << ' ';

    return 0;
}

#endif // _Pbrngw_

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