Submission #910205

#	Time	Username	Problem	Language	Result	Execution time	Memory
910205		biank	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	9 ms	860 KiB

longesttrip

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define pb push_back
typedef vector<int> vi;
bool are_connected(vi A, vi B);

vi longest_trip(int N, int D) {
    (void)D;
    queue<vi> q;
    forn(i,N) q.push({i});
    auto plop = [&](){
      vi x = q.front();
      q.pop();
      return x;  
    };
    while(SIZE(q)>=3) {
        vi a = plop(),
           b = plop(),
           c = plop();
        if(are_connected({a.back()},{b.front()})) {
            forn(i,SIZE(b)) a.pb(b[i]);
            q.push(a), q.push(c);
        } else if(are_connected({a.back()},{c.front()})) {
            forn(i,SIZE(c)) a.pb(c[i]);
            q.push(a), q.push(b);
        } else {
            reverse(ALL(b));
            forn(i,SIZE(c)) b.pb(c[i]);
            q.push(b), q.push(a);
        }
    }
    vi a = plop(), b = plop();
    if(SIZE(b)>SIZE(a)) swap(a,b);
    if(b.empty() || !are_connected(a,b)) return a;
    
    vi qa = {a.front()};
    if(a.back() != qa.back()) qa.pb(a.back());
    vi qb = {b.front()};
    if(b.back() != qb.back()) qb.pb(b.back());
    
    if(are_connected(qa, qb)) {
        if(are_connected({a.back()}, {b.front()})) {
            forn(i,SIZE(b)) a.pb(b[i]);
            return a;
        }
        
        if(are_connected({b.back()}, {a.front()})) {
            forn(i,SIZE(a)) b.pb(a[i]);
            return b;
        }
        
        if(are_connected({a.front()},{b.front()})) {
            reverse(ALL(a));
            forn(i,SIZE(b)) a.pb(b[i]);
            return a;
        }
        
        if(are_connected({a.back()}, {b.back()})) {
            reverse(ALL(b));
            forn(i,SIZE(b)) a.pb(b[i]);
            return a;
        }
        
    }
    
    int l=0, r=SIZE(a);
    while(l+1<r) {
        int m=(l+r)/2;
        if(are_connected(b,vi(a.begin()+m,a.begin()+r))) l=m;
        else r=m;
    }
    
    int i=l;
    
    l=0, r=SIZE(b);
    while(l+1<r) {
        int m=(l+r)/2;
        if(are_connected({a[i]},vi(b.begin()+m,b.begin()+r))) l=m;
        else r=m;
    }
    
    int j=l;
    
    vi ans;
    forsn(p,i+1,SIZE(a)) ans.pb(a[p]);
    forn(p,i+1) ans.pb(a[p]);
    forsn(p,j+1,SIZE(b)) ans.pb(b[p]);
    forn(p,j+1) ans.pb(b[p]);
    
    return ans;
}

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