Submission #1217972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217972		qwusha	가장 긴 여행 (IOI23_longesttrip)	C++20	0 / 100	1 ms	420 KiB

longesttrip

#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;


vector<int> s;
vector<int> used;
int n;
int endik = -1;

/*
bool are_connected(vector<int> a, vector<int> b) {
    cout <<endl << "QUERY" << endl;
    for (auto el : a) {
        cout << el << " ";
    }
    cout << endl << "and" << endl;
    for (auto el : b) {
        cout << el << " ";
    }
    cout << endl;

    int x;
    cin >> x;
    return (x == 1);
}
*/


vector<int> longest_trip(int N, int d) {
    n = N;
    vector<int> p, q;
    p.push_back(0);
    for (int i = 1; i < n; i++) {
        if (are_connected({0}, {i})) {
            p.push_back(i);
        } else {
            q.push_back(i);
        }
    }
    if (are_connected(p, q)) {
        int m = q.size();
        int l = -1, r = m-1;
        vector<int> pa;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            pa.clear();
            for (int i = 0; i <= mid; i++) {
                pa.push_back(q[i]);
            }
            if (are_connected(p, pa)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        int conq = q[r];
        m = p.size();
        l = -1;
        r = m - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            pa.clear();
            for (int i = 0; i <= mid; i++) {
                pa.push_back(p[i]);
            }
            if (are_connected(pa, {conq})) {
                r = mid;
            } else {
                l = mid;
            }
        }
        int conp = p[r];
        vector<int> res;
        for (auto el : q) {
            if (el != conq) {
                res.push_back(el);
            }
        }
        res.push_back(conq);
        res.push_back(conp);
        for (auto el : p) {
            if (el != conp) {
                res.push_back(el);
            }
        }
        return res;
    } else {
        if (p.size() < q.size()) {
            swap(p, q);
        }
        return p;
    }
}

/*
signed main() {
    int N, D;
    cin >> N >> D;
    auto res = longest_trip(N, D);
    for (auto el : res) {
        cout << el << ' ';
    }
    cout << endl;
}
*/

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