Submission #1310389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310389		AliMark71	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	9 ms	456 KiB

longesttrip

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

template<typename T>
using vec = std::vector<T>;
using namespace std;

struct xlist {
    struct node {
        int storage;
        uintptr_t npx = 0;
        node *next(node* prev) {
            return (node*)(npx ^ (uintptr_t)prev);
        }
    };
    
    node *head = nullptr, *tail = nullptr;
    int size = 0;
    
    xlist(initializer_list<int> list) {
        if (list.size() == 0) return;
        size = 1;
        head = tail = new node{ .storage = *list.begin() };
        for (auto it = next(list.begin()); it != list.end(); ++it)
            append(*it);
    }
    
    xlist(node *head, node* tail, int size) : head(head), tail(tail), size(size) {}
    
    void append(int a) {
        if (size == 0) {
            *this = xlist{a};
            return;
        }
        
        node *t = new node{ .storage = a };
        t->npx = (uintptr_t)tail;
        tail->npx ^= (uintptr_t)t;
        tail = t;
        size++;
    }
    
    void concat(xlist &l) {
        if (size == 0) {
            *this = l;
            return;
        }
        if (l.size == 0)
            return;
        
        tail->npx ^= (uintptr_t)l.head;
        l.head->npx ^= (uintptr_t)tail;
        tail = l.tail;
        size += l.size;
        
        l.size = 0;
        l.head = l.tail = nullptr;
    }
    
    int front() {
        return head->storage;
    }
    int back() {
        return tail->storage;
    }
    
    void reverse() {
        swap(head, tail);
    }
    
    vec<int> collect() {
        vec<int> res;
        
        node* prev = nullptr;
        node* curr = head;
        while (curr != nullptr) {
            res.push_back(curr->storage);
            
            node* next = curr->next(prev);
            prev = curr;
            curr = next;
        }
        return res;
    }
    
    array<xlist, 2> cut(int i) {
        assert(i < size - 1);
        
        node* prev = nullptr;
        node* curr = head; int curr_i = 0;
        while (curr_i < i) {
            node* next = curr->next(prev);
            prev = curr;
            curr = next; curr_i++;
        }
        
        node* atail = curr;
        node* bhead = curr->next(prev);
        atail->npx ^= (uintptr_t)bhead;
        bhead->npx ^= (uintptr_t)atail;
        
        xlist a(head, atail, i + 1),
              b(bhead, tail, size - i - 1);
        return {a, b};
    }
};

std::vector<int> longest_trip(int N, int D)
{
    vec<int> nodes(N); for (int i = 0; i < N; i++) nodes[i] = i;
    if (D == 3)
        return nodes;
    if (D == 2) {
        deque<int> path{0, are_connected({0}, {1}) ? 1 : 2};
        nodes.erase(find(nodes.begin(), nodes.end(), path.front()));
        nodes.erase(find(nodes.begin(), nodes.end(), path.back()));
        
        while (!nodes.empty()) {
            auto u = nodes.back(); nodes.pop_back();
            if (are_connected({path.front()}, {u}))
                path.push_front(u);
            else
                path.push_back(u);
        }
        
        return vec<int>(path.begin(), path.end());
    }
    
    xlist path[2] = {{0}, {1}};
    nodes.erase(find(nodes.begin(), nodes.end(), path[0].back()));
    nodes.erase(find(nodes.begin(), nodes.end(), path[1].back()));
    while (!nodes.empty()) {
        auto u = nodes.back(); nodes.pop_back();
        if (are_connected({path[0].back()}, {u}))
            path[0].append(u);
        else if (are_connected({path[1].back()}, {u}))
            path[1].append(u);
        else {
            path[1].reverse();
            path[0].concat(path[1]);
            path[1].append(u);
        }
    }
    
    bool connected = true;
    if (are_connected({path[0].front()}, {path[1].front()})) {
        path[0].reverse();
        path[0].concat(path[1]);
    } else if (are_connected({path[0].front()}, {path[1].back()})) {
        path[1].concat(path[0]);
        path[0] = path[1];
    } else // p1.f <-> p1.b;
        connected = false;
    if (connected)
        return path[0].collect();
    
    connected = true;
    if (are_connected({path[0].back()}, {path[1].front()}))
        path[0].concat(path[1]);
    else if (are_connected({path[0].back()}, {path[1].back()})) {
        path[1].reverse();
        path[0].concat(path[1]);
    } else // p2.f <-> p2.b;
        connected = false;
    if (connected)
        return path[0].collect();
    
    vec<int> p0 = path[0].collect(), p1 = path[1].collect();
    
    if (!are_connected(p0, p1))
        return p0.size() > p1.size() ? p0 : p1;
    
    int a = 0, b = 0;
    if (1 < p0.size()) {
        int l = 0, r = (int) p0.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (are_connected(vec<int>(p0.begin() + l, p0.begin() + mid + 1), p1))
                r = mid;
            else
                l = mid + 1;
        }
        
        a = l;
    }
    
    if (1 < p1.size()) {
        int l = 0, r = (int) p1.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (are_connected(p0, vec<int>(p1.begin() + l, p1.begin() + mid + 1)))
                r = mid;
            else
                l = mid + 1;
        }
        
        b = l;
    }
    
    if (1 < p0.size() && 1 < p1.size()) {
        auto [p0a, p0b] = path[0].cut(a);
        auto [p1a, p1b] = path[1].cut(b);
        
        p1a.reverse();
        p1b.reverse();
        p0b.concat(p0a);
        p0b.concat(p1a);
        p0b.concat(p1b);
        
        return p0b.collect();
    }
     
    if (p0.size() == 1) {
        swap(p0, p1);
        swap(a, b);
        swap(path[0], path[1]);
    }
    
    auto [pa, pb] = path[0].cut(a);
    pb.concat(pa);
    pb.concat(path[1]);
    
    return pb.collect();
}

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