Submission #1233264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233264		Ghulam_Junaid	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	1 ms	428 KiB

longesttrip

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

const int N = 256;
int n, d;
int store[N][N];

bool query(vector<int> a, vector<int> b){
    if (a.empty() or b.empty()) return 0;
    if (a.size() > 1 or b.size() > 1)
        return are_connected(a, b);
    if (store[a[0]][b[0]]) return store[a[0]][b[0]] - 1;
    bool res = are_connected(a, b);
    store[a[0]][b[0]] = 1 + res;
    return res;
}

vector<int> longest_trip(int nn, int dd){
    n = nn, d = dd;
    vector<int> res;

    if (d > 1){
        deque<int> dq;
        if (query({0}, {1})){
            dq.push_back(0), dq.push_back(1);
            for (int i = 2; i < n; i ++){
                if (query({dq.back()}, {i}))
                    dq.push_back(i);
                else
                    dq.push_front(i);
            }
            for (int x : dq)
                res.push_back(x);
            return res;
        }
        dq.push_back(0); dq.push_back(2); dq.push_back(1);
        for (int i = 3; i < n; i ++){
            if (query({dq.back()}, {i}))
                dq.push_back(i);
            else
                dq.push_front(i);
        }
        for (int x : dq)
            res.push_back(x);
        return res;
    }

    vector<int> chain1, chain2;
    chain1.push_back(0);
    for (int i = 1; i < n; i ++){
        if (query({chain1.back()}, {i})){
            chain1.push_back(i);
            continue;
        }
        if (chain2.empty() or query({chain2.back()}, {i})){
            chain2.push_back(i);
            continue;
        }
        reverse(chain2.begin(), chain2.end());
        for (int x : chain2)
            chain1.push_back(x);
        chain2 = {i};
    }

    if (!query(chain1, chain2)){
        if (chain1.size() > chain2.size()) return chain1;
        return chain2;
    }

    if (query({chain1[0]}, {chain2.back()})){
        for (int x : chain1) chain2.push_back(x);
        return chain2;
    }

    if (query({chain1.back()}, {chain2.back()})){
        reverse(chain2.begin(), chain2.end());
        for (int x : chain2) chain1.push_back(x);
        return chain1;
    }

    if (query({chain2[0]}, {chain1[0]})){
        reverse(chain2.begin(), chain2.end());
        for (int x : chain1) chain2.push_back(x);
        return chain2;
    }

    if (query({chain2[0]}, {chain1.back()})){
        for (int x : chain2) chain1.push_back(x);
        return chain1;
    }

    int l = -1, r = chain1.size() - 1;
    while (r - l > 1){
        int mid = (l + r) / 2;

        vector<int> vec;
        for (int i = 0; i <= mid; i ++)
            vec.push_back(chain1[i]);
        
        if (query(vec, chain2)) r = mid;
        else l = mid;
    }

    vector<int> vec;
    for (int i = 0; i <= r; i ++)
        vec.push_back(chain1[i]);

    int P = r;

    l = -1, r = chain2.size() - 1;
    while (r - l > 1){
        int mid = (l + r) / 2;

        vector<int> vec2;
        for (int i = 0; i <= mid; i ++)
            vec2.push_back(chain2[i]);
        
        if (query(vec2, vec)) r = mid;
        else l = mid;
    }

    vector<int> vec2;
    for (int i = 0; i <= r; i ++)
        vec2.push_back(chain2[i]);

    int Q = r;

    for (int i = P + 1; i < chain1.size(); i ++)
        res.push_back(chain1[i]);
    for (int i = 0; i <= P; i ++)
        res.push_back(chain1[i]);

    for (int i = Q; i < chain2.size(); i ++)
        res.push_back(chain2[i]);
    for (int i = 0; i < Q; i ++)
        res.push_back(chain2[i]);

    return res;
}

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