제출 #937465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937465		GrindMachine	가장 긴 여행 (IOI23_longesttrip)	C++17	15 / 100	33 ms	1368 KiB

longesttrip

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
 
/*
 
already knew the solution
 
*/
 
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
 
#include "longesttrip.h"
 
std::vector<int> longest_trip(int n, int d)
{
    vector<deque<int>> paths;
    rep(i,n){
        paths.pb({i});
    }
 
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int q = 0;

    while(sz(paths) >= 3){
        int siz = sz(paths);
        vector<int> ord(siz);
        rep(i,siz) ord[i] = i;
        shuffle(all(ord),rng);
 
        auto p1 = paths[ord[0]];
        auto p2 = paths[ord[1]];
        auto p3 = paths[ord[2]];
 
        vector<deque<int>> new_paths;
        rep(i,siz){
            bool ok = true;
            rep(j,3){
                if(i == ord[j]){
                    ok = false;
                }
            }
 
            if(ok){
                new_paths.pb(paths[i]);
            }
        }
 
        int u = p1[0], v = p2[0], w = p3[0];
 
        if(are_connected({u},{v})){
            q++;
            while(!p2.empty()){
                p1.push_front(p2.front());
                p2.pop_front();
            }
        }
        else if(are_connected({u},{w})){
            q += 2;
            while(!p3.empty()){
                p1.push_front(p3.front());
                p3.pop_front();
            }
        }
        else{
            q += 2;
            while(!p3.empty()){
                p2.push_front(p3.front());
                p3.pop_front();
            }
        }
 
        if(!p1.empty()){
            new_paths.pb(p1);
        }
        if(!p2.empty()){
            new_paths.pb(p2);
        }
        if(!p3.empty()){
            new_paths.pb(p3);
        }
 
        paths = new_paths;
    }
 
    auto p1 = paths[0], p2 = paths[1];
    if(are_connected({p1[0]},{p2[0]})){
        q++;
        while(!p2.empty()){
            p1.push_front(p2.front());
            p2.pop_front();
        }
    }
    else if(are_connected({p1[0]},{p2.back()})){
        q += 2;
        while(!p2.empty()){
            p1.push_front(p2.back());
            p2.pop_back();
        }
    }
    else if(are_connected({p1.back()},{p2[0]})){
        q += 3;
        while(!p2.empty()){
            p1.pb(p2.front());
            p2.pop_front();
        }
    }
    else if(are_connected({p1.back()},{p2.back()})){
        q += 4;
        while(!p2.empty()){
            p1.pb(p2.back());
            p2.pop_back();
        }
    }
 
    if(p2.empty()){
        return vector<int>(all(p1));
    }
 
    int l = 0, r = sz(p1)-1;
    int pos1 = -1;
 
    while(l <= r){
        int mid = (l+r) >> 1;
        vector<int> v1;
        rep(i,mid+1){
            v1.pb(p1[i]);
        }
        vector<int> v2(all(p2));

        q++;
 
        if(are_connected(v1,v2)){
            pos1 = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
 
    if(pos1 == -1){
        if(sz(p1) > sz(p2)){
            return vector<int>(all(p1));
        }
        else{
            return vector<int>(all(p2));
        }
    }
 
    l = 0, r = sz(p2)-1;
    int pos2 = -1;
 
    while(l <= r){
        int mid = (l+r) >> 1;
        vector<int> v1 = {p1[pos1]};
        vector<int> v2;
        rep(i,mid+1){
            v2.pb(p2[i]);
        }
    
        q++;

        if(are_connected(v1,v2)){
            pos2 = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
 
    assert(pos2 != -1);
    assert(q <= 410);

    rotate(p1.begin(),p1.begin()+pos1,p1.end());
    rotate(p2.begin(),p2.begin()+pos2,p2.end());
 
    while(!p2.empty()){
        p1.push_front(p2.front());
        p2.pop_front();
    }
 
    return vector<int>(all(p1));
}

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