oj.uz

Submission #903956

# Submission time Handle Problem Language Result Execution time Memory
903956 2024-01-11T15:31:46 Z LaviniaTornaghi Longest Trip (IOI23_longesttrip) C++17
25 / 100
 11 ms 1384 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;

struct XorList {
    struct Node {
        int val;
        Node *x, *y;

        Node(int val) : val(val), x(NULL), y(NULL) { }
    } *start, *end;

    void merge(XorList *o) {
        if (end->x == NULL) {
            end->x = o->start;
        } else {
            end->y = o->start;
        }

        if (o->start->x == NULL) {
            o->start->x = end;
        } else {
            o->start->y = end;
        }

        end = o->end;
        o->start = o->end = NULL;
    }

    vector<int> vectorize() {
        vector<int> ans;
        
        Node* curr = start, *old = NULL;
        while (curr != NULL) {
            ans.push_back(curr->val);

            if (old == curr->x) {
                old = curr;
                curr = old->y;
            } else {
                old = curr;
                curr = old->x;
            }
        }
        return ans;
    }

    int first() { return start->val; }
    int last() { return end->val; }
    void reverse() { swap(start, end); }
    XorList(int val) { start = end = new Node(val); }
};

vector<int> longest_trip(int N, int D) {
    XorList *a = new XorList(0);
    XorList *b = new XorList(1);
    
    for (int i = 2; i < N; i++) {
        int last_a = a->last();
        int last_b = b->last();
        XorList *m = new XorList(i);

        if (are_connected({last_a}, {last_b})) {
            b->reverse();
            a->merge(b);

            b = m;
        } else if (are_connected({last_a}, {i})) {
            a->merge(m);
        } else {
            b->merge(m);
        }
    }

    /*if (are_connected({a->first()}, {b->first()})) {
        a->reverse();
        a->merge(b);
        return a->vectorize();
    }

    if (are_connected({a->first()}, {b->last()})) {
        a->reverse();
        b->reverse();
        a->merge(b);
        return a->vectorize();
    }

    if (are_connected({a->last()}, {b->first()})) {
        a->merge(b);
        return a->vectorize();
    }

    if (are_connected({a->last()}, {b->last()})) {
        b->reverse();
        a->merge(b);
        return a->vectorize();
    }*/

    vector<int> chain_a = a->vectorize();
    vector<int> chain_b = b->vectorize();
    return chain_a.size() > chain_b.size() ? chain_a : chain_b;

    int l1 = -1, r1 = chain_a.size();
    while (l1 + 1 < r1) {
        int m = (l1 + r1) / 2;
        if (are_connected(vector<int>(chain_a.begin(), chain_a.begin() + m + 1), chain_b)) {
            r1 = m;
        } else {
            l1 = m;
        }
    }

    if (r1 == chain_a.size()) {
        return chain_a.size() > chain_b.size() ? chain_a : chain_b;
    }

    int l2 = -1, r2 = chain_b.size();
    while (l2 + 1 < r2) {
        int m = (l2 + r2) / 2;
        if (are_connected(vector<int>(chain_b.begin(), chain_b.begin() + m + 1), {r1})) {
            r2 = m;
        } else {
            l2 = m;
        }
    }

    rotate(chain_a.begin(), chain_a.begin() + r1 + 1, chain_a.end());
    rotate(chain_b.begin(), chain_b.begin() + r2, chain_b.end());
    copy(chain_b.begin(), chain_b.end(), back_inserter(chain_a));

    return chain_a;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:113:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     if (r1 == chain_a.size()) {
      |         ~~~^~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 5 ms 1140 KB Output is correct
3 Correct 4 ms 744 KB Output is correct
4 Correct 5 ms 856 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 6 ms 612 KB Output is correct
7 Correct 7 ms 612 KB Output is correct
8 Correct 5 ms 980 KB Output is correct
9 Correct 5 ms 988 KB Output is correct
10 Correct 5 ms 980 KB Output is correct
11 Correct 6 ms 976 KB Output is correct
12 Correct 5 ms 1000 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 5 ms 612 KB Output is correct
15 Correct 8 ms 612 KB Output is correct
16 Correct 7 ms 1124 KB Output is correct
17 Correct 7 ms 972 KB Output is correct
18 Correct 8 ms 888 KB Output is correct
19 Correct 6 ms 912 KB Output is correct
20 Correct 5 ms 888 KB Output is correct
21 Correct 5 ms 960 KB Output is correct
22 Correct 5 ms 1128 KB Output is correct
23 Correct 7 ms 1376 KB Output is correct
24 Correct 5 ms 880 KB Output is correct
25 Correct 6 ms 856 KB Output is correct
26 Correct 6 ms 968 KB Output is correct
27 Correct 5 ms 856 KB Output is correct
28 Correct 7 ms 716 KB Output is correct
29 Correct 8 ms 704 KB Output is correct
30 Correct 8 ms 948 KB Output is correct
31 Correct 10 ms 972 KB Output is correct
32 Correct 9 ms 1224 KB Output is correct
33 Correct 7 ms 1104 KB Output is correct
34 Correct 9 ms 1136 KB Output is correct
35 Correct 8 ms 1112 KB Output is correct
36 Correct 7 ms 1132 KB Output is correct
37 Correct 9 ms 856 KB Output is correct
38 Correct 10 ms 736 KB Output is correct
39 Correct 9 ms 972 KB Output is correct
40 Correct 10 ms 1112 KB Output is correct
41 Correct 10 ms 1148 KB Output is correct
42 Correct 9 ms 724 KB Output is correct
43 Correct 11 ms 1368 KB Output is correct
44 Correct 11 ms 1240 KB Output is correct
45 Correct 6 ms 980 KB Output is correct
46 Correct 6 ms 600 KB Output is correct
47 Correct 8 ms 1108 KB Output is correct
48 Correct 8 ms 600 KB Output is correct
49 Correct 8 ms 1112 KB Output is correct
50 Correct 6 ms 692 KB Output is correct
51 Correct 8 ms 1204 KB Output is correct
52 Correct 8 ms 944 KB Output is correct
53 Correct 8 ms 856 KB Output is correct
54 Correct 9 ms 892 KB Output is correct
55 Correct 9 ms 1132 KB Output is correct
56 Correct 6 ms 864 KB Output is correct
57 Correct 10 ms 1384 KB Output is correct
58 Correct 10 ms 1384 KB Output is correct
59 Correct 9 ms 876 KB Output is correct
60 Correct 9 ms 980 KB Output is correct
61 Correct 9 ms 868 KB Output is correct
62 Correct 10 ms 972 KB Output is correct
63 Correct 10 ms 1240 KB Output is correct
64 Correct 8 ms 856 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -