Submission #1243254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243254		nvujica	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	4 ms	416 KiB

longesttrip

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

using namespace std;

map <pair<vector<int>, vector <int> >, int> memo;

bool are(vector <int> a, vector <int> b){
    // return are_connected(a, b);

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	
	if(memo.find({a, b}) != memo.end()) return memo[{a, b}];
	
	return memo[{a, b}] = are_connected(a, b);
}

vector<int> longest_trip(int n, int d){
    memo.clear();
    
    srand(time(0));

    vector <int> v;
    for(int i = 0; i < n; i++) v.push_back(i);

//    // int dosta = n * n;
//
//    // for(int i = 0; i < dosta; i++){
//    //     int p1 = rand() % n;
//    //     int p2 = rand() % n;
//
//    //     if(p1 != p2) swap(v[p1], v[p2]);
//    // }

    vector <int> a, b;

    a.push_back(v[0]);
    // b.push_back(v[1]);

    bool znam = 0;

    for(int i = 1; i < n; i++){
        // if(rand() % 2) swap(a, b);
        
        if(are({a.back()}, {v[i]})){
            a.push_back(v[i]);
            znam = 0;
        }
        else if(znam || are({b.back()}, {v[i]})){
            b.push_back(v[i]);
            znam = 0;
        }
        else {
            while(!b.empty()){
                a.push_back(b.back());
                b.pop_back();
            }
            b.push_back(v[i]);
            znam = 1;
        }
    }

    if(a.size() < b.size()) swap(a, b);
    if(a.size() == n) return a;
    if(!are(a, b)) return a;

	if(are({a[0], a.back()}, {b[0], b.back()})){
        if(are({a.back()}, {b[0]})){
            for(int i = 0; i < b.size(); i++){
                a.push_back(b[i]);
            }

            return a;
        }

        if(are({a.back()}, {b.back()})){
            for(int i = b.size() - 1; i >= 0; i--){
                a.push_back(b[i]);
            }

            return a;
        }

        if(are({b.back()}, {a[0]})){
            for(int i = 0; i < a.size(); i++){
                b.push_back(a[i]);
            }

            return b;
        }

        if(are({a[0]}, {b[0]})){
            reverse(b.begin(), b.end());
            
            for(int i = 0; i < a.size(); i++){
                b.push_back(a[i]);
            }

            return b;
        }
    }

    int lo = 1, hi = a.size();

    while(lo < hi){
        int mid = (lo + hi) / 2;

        v.clear();

        for(int i = 0; i < mid; i++){
            v.push_back(a[i]);
        }
        
        if(are(v, b)) hi = mid;
        else lo = mid + 1;
    }

    v.clear();

    for(int i = hi; i < a.size(); i++) v.push_back(a[i]);
    for(int i = 0; i < hi; i++) v.push_back(a[i]);

    a = v;

    lo = 1, hi = b.size();

    while(lo < hi){
        int mid = (lo + hi) / 2;

        v.clear();

        for(int i = 0; i < mid; i++){
            v.push_back(b[i]);
        }

        if(are({a.back()}, v)) hi = mid;
        else lo = mid + 1;
    }

    for(int i = hi - 1; i < b.size(); i++) a.push_back(b[i]);
    for(int i = 0; i < hi - 1; i++) a.push_back(b[i]);

    return a;
}

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