oj.uz

Submission #849762

# Submission time Handle Problem Language Result Execution time Memory
849762 2023-09-15T09:31:55 Z MuntherCarrot Longest Trip (IOI23_longesttrip) C++17
100 / 100
 14 ms 852 KB 
// by me
#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()

bool are_connected(std::vector<int> A, std::vector<int> B);
bool con(vector<int> a, vector<int> b){
    return are_connected(a, b);
}

std::vector<int> longest_trip(int N, int D)
{
    vector<int> v1 = {0}, v2 = {1};
    for(int i = 2; i < N; i++){
        if(i == N - 1){
            // con?(a, b) -> mrg(a, b)
            if(con({v1.back()}, {N - 1})){
                v1.push_back(N - 1);
            }
            // con?(c, b) -> mrg(c, b)
            else if(con({v2.back()}, {N - 1})){
                v2.push_back(N - 1);
            }
            // mrg(a, c)
            else{
                for(int i = v2.size() - 1; i >= 0; i--){
                    v1.push_back(v2[i]);
                }
                v2 = {N - 1};
            }
        }
        else{
            // con?(a, b) -> mrg(a, b)
            if(con({v1.back()}, {i})){
                v1.push_back(i);
            }
            // con?(c, b) -> mrg(c, b)
            else if(con({v2.back()}, {i})){
                v2.push_back(i);
                // con?(b, d) -> mrg(b, d) : mrg(a, d)
                if(con({i}, {i + 1})){
                    v2.push_back(i + 1);
                }
                else{
                    v1.push_back(i + 1);
                }
                i++;
            }
            // con?(b, d) -> mrg(b, d), mrg(a, c)
            else if(con({i}, {i + 1})){
                for(int j = v2.size() - 1; j >= 0; j--){
                    v1.push_back(v2[j]);
                }
                v2 = {i, i + 1};
                i++;
            }
            // mrg(d, c), mrg(a, c);
            else{
                v2.push_back(i + 1);
                for(int j = v2.size() - 1; j >= 0; j--){
                    v1.push_back(v2[j]);
                }
                v2 = {i};
                i++;
            }
        }
    }
    // !con?(v1, v2);
    if(!con(v1, v2)){
        return v1.size() > v2.size() ? v1 : v2;
    }
    // con?(v1, v2)
    if(con({v1.back()}, {v2.back()})){
        for(int i = v2.size() - 1; i >= 0; i--){
            v1.push_back(v2[i]);
        }
        return v1;
    }
    if(con({v1[0]}, {v2.back()})){
        reverse(all(v1));
        for(int i = v2.size() - 1; i >= 0; i--){
            v1.push_back(v2[i]);
        }
        return v1;
    }
    if(con({v1.back()}, {v2[0]})){
        for(int i = 0; i < v2.size(); i++){
            v1.push_back(v2[i]);
        }
        return v1;
    }
    if(con({v1[0]}, {v2[0]})){
        reverse(all(v1));
        for(int i = 0; i < v2.size(); i++){
            v1.push_back(v2[i]);
        }
        return v1;
    }

    vector<int> ans;
    int l1 = 0, r1 = v1.size() - 1, k1 = 0;
    while(l1 <= r1){
        int mid = (l1 + r1) / 2;
        vector<int> f;
        for(int i = l1; i <= mid; i++){
            f.push_back(v1[i]);
        }
        if(con(f, v2)){
            r1 = mid - 1;
            k1 = mid;
        }
        else{
            l1 = mid + 1;
        }
    }
    for(int i = 0; i < v1.size(); i++){
        int j = (i + k1) % v1.size();
        ans.push_back(v1[j]);
    }
    reverse(all(ans));

    int l2 = 0, r2 = v2.size() - 1, k2 = 0;
    while(l2 <= r2){
        int mid = (l2 + r2) / 2;
        vector<int> f;
        for(int i = l2; i <= mid; i++){
            f.push_back(v2[i]);
        }
        if(con(f, {v1[k1]})){
            r2 = mid - 1;
            k2 = mid;
        }
        else{
            l2 = mid + 1;
        }
    }
    for(int i = 0; i < v2.size(); i++){
        int j = (i + k2) % v2.size();
        ans.push_back(v2[j]);
    }
    return ans;
}
//
/*
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>


static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
    printf("Protocol Violation: %s\n", message.c_str());
    exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
    ++call_counter;
    ++total_call_counter;
    if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
    {
        protocol_violation("too many calls");
    }

    int nA = A.size(), nB = B.size();
    landmark_counter += nA + nB;
    if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
    {
        protocol_violation("too many elements");
    }

    if (nA == 0 || nB == 0)

        protocol_violation("invalid array");
    }
    for (int i = 0; i < nA; ++i)
    {
        if (A[i] < 0 || N <= A[i])
        {
            protocol_violation("invalid array");
        }
        if (present[A[i]])
        {
            protocol_violation("invalid array");
        }
        present[A[i]] = true;
    }
    for (int i = 0; i < nA; ++i)
    {
        present[A[i]] = false;
    }
    for (int i = 0; i < nB; ++i)
    {
        if (B[i] < 0 || N <= B[i])
        {
            protocol_violation("invalid array");
        }
        if (present[B[i]])
        {
            protocol_violation("invalid array");
        }
        present[B[i]] = true;
    }
    for (int i = 0; i < nB; ++i)
    {
        present[B[i]] = false;
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (A[i] == B[j])
            {
                protocol_violation("non-disjoint arrays");
            }
        }
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
            {
                return true;
            }
        }
    }

    return false;
}

int main()
{
    assert(1 == scanf("%d", &C));
    int maximumCalls = 0;
    for (int c = 0; c < C; ++c)
    {
        call_counter = 0;
        assert(2 == scanf("%d %d", &N, &D));

        present.assign(N, false);
        U.resize(N);
        for (int i = 1; i < N; ++i)
        {
            U[i].resize(i);
            for (int j = 0; j < i; ++j)
            {
                assert(1 == scanf("%d", &U[i][j]));
            }
        }

        for (int i = 2; i < N; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (U[i][j] + U[i][k] + U[j][k] < D)
                    {
                        printf("Insufficient Density\n");
                        exit(0);
                    }
                }
            }
        }

        std::vector<int> t = longest_trip(N, D);
        int l = t.size();
        printf("%d\n", l);
        for (int i = 0; i < l; ++i)
        {
            printf(i == 0 ? "%d" : " %d", t[i]);
        }
        printf("\n");
        printf("%d\n", call_counter);

        maximumCalls = std::max(maximumCalls, call_counter);
        call_counter = 0;
    }
    printf("%d\n", maximumCalls);

    return 0;
}
//*/
// by me

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i = 0; i < v2.size(); i++){
      |                        ~~^~~~~~~~~~~
longesttrip.cpp:98:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int i = 0; i < v2.size(); i++){
      |                        ~~^~~~~~~~~~~
longesttrip.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i = 0; i < v1.size(); i++){
      |                    ~~^~~~~~~~~~~
longesttrip.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < v2.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 436 KB Output is correct
11 Correct 5 ms 440 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 4 ms 440 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 5 ms 440 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 4 ms 436 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 8 ms 340 KB Output is correct
16 Correct 9 ms 344 KB Output is correct
17 Correct 5 ms 600 KB Output is correct
18 Correct 5 ms 600 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 5 ms 344 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 5 ms 696 KB Output is correct
23 Correct 5 ms 600 KB Output is correct
24 Correct 5 ms 436 KB Output is correct
25 Correct 6 ms 344 KB Output is correct
26 Correct 6 ms 344 KB Output is correct
27 Correct 7 ms 344 KB Output is correct
28 Correct 5 ms 344 KB Output is correct
29 Correct 6 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 6 ms 344 KB Output is correct
33 Correct 5 ms 600 KB Output is correct
34 Correct 5 ms 600 KB Output is correct
35 Correct 6 ms 756 KB Output is correct
36 Correct 5 ms 344 KB Output is correct
37 Correct 6 ms 344 KB Output is correct
38 Correct 6 ms 600 KB Output is correct
39 Correct 5 ms 344 KB Output is correct
40 Correct 6 ms 344 KB Output is correct
41 Correct 7 ms 344 KB Output is correct
42 Correct 7 ms 600 KB Output is correct
43 Correct 6 ms 608 KB Output is correct
44 Correct 6 ms 344 KB Output is correct
45 Correct 9 ms 596 KB Output is correct
46 Correct 9 ms 344 KB Output is correct
47 Correct 9 ms 344 KB Output is correct
48 Correct 10 ms 344 KB Output is correct
49 Correct 7 ms 344 KB Output is correct
50 Correct 5 ms 344 KB Output is correct
51 Correct 8 ms 432 KB Output is correct
52 Correct 14 ms 344 KB Output is correct
53 Correct 5 ms 344 KB Output is correct
54 Correct 5 ms 344 KB Output is correct
55 Correct 7 ms 344 KB Output is correct
56 Correct 4 ms 440 KB Output is correct
57 Correct 5 ms 612 KB Output is correct
58 Correct 7 ms 600 KB Output is correct
59 Correct 7 ms 600 KB Output is correct
60 Correct 8 ms 692 KB Output is correct
61 Correct 7 ms 432 KB Output is correct
62 Correct 8 ms 684 KB Output is correct
63 Correct 7 ms 600 KB Output is correct
64 Correct 7 ms 436 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 6 ms 440 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 440 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 8 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 7 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 5 ms 344 KB Output is correct
21 Correct 7 ms 344 KB Output is correct
22 Correct 7 ms 344 KB Output is correct
23 Correct 7 ms 340 KB Output is correct
24 Correct 7 ms 344 KB Output is correct
25 Correct 5 ms 344 KB Output is correct
26 Correct 4 ms 344 KB Output is correct
27 Correct 5 ms 344 KB Output is correct
28 Correct 6 ms 344 KB Output is correct
29 Correct 5 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 5 ms 436 KB Output is correct
32 Correct 9 ms 344 KB Output is correct
33 Correct 10 ms 344 KB Output is correct
34 Correct 9 ms 344 KB Output is correct
35 Correct 9 ms 344 KB Output is correct
36 Correct 9 ms 344 KB Output is correct
37 Correct 5 ms 344 KB Output is correct
38 Correct 7 ms 436 KB Output is correct
39 Correct 7 ms 344 KB Output is correct
40 Correct 6 ms 600 KB Output is correct
41 Correct 5 ms 344 KB Output is correct
42 Correct 5 ms 344 KB Output is correct
43 Correct 5 ms 440 KB Output is correct
44 Correct 5 ms 432 KB Output is correct
45 Correct 5 ms 440 KB Output is correct
46 Correct 6 ms 432 KB Output is correct
47 Correct 4 ms 344 KB Output is correct
48 Correct 5 ms 344 KB Output is correct
49 Correct 6 ms 600 KB Output is correct
50 Correct 6 ms 344 KB Output is correct
51 Correct 6 ms 344 KB Output is correct
52 Correct 5 ms 600 KB Output is correct
53 Correct 6 ms 344 KB Output is correct
54 Correct 5 ms 344 KB Output is correct
55 Correct 6 ms 344 KB Output is correct
56 Correct 4 ms 344 KB Output is correct
57 Correct 5 ms 344 KB Output is correct
58 Correct 8 ms 344 KB Output is correct
59 Correct 6 ms 344 KB Output is correct
60 Correct 6 ms 344 KB Output is correct
61 Correct 5 ms 600 KB Output is correct
62 Correct 5 ms 600 KB Output is correct
63 Correct 6 ms 600 KB Output is correct
64 Correct 7 ms 600 KB Output is correct
65 Correct 7 ms 444 KB Output is correct
66 Correct 6 ms 440 KB Output is correct
67 Correct 6 ms 444 KB Output is correct
68 Correct 8 ms 592 KB Output is correct
69 Correct 6 ms 436 KB Output is correct
70 Correct 6 ms 436 KB Output is correct
71 Correct 5 ms 436 KB Output is correct
72 Correct 6 ms 444 KB Output is correct
73 Correct 7 ms 444 KB Output is correct
74 Correct 8 ms 604 KB Output is correct
75 Correct 7 ms 344 KB Output is correct
76 Correct 7 ms 344 KB Output is correct
77 Correct 5 ms 440 KB Output is correct
78 Correct 6 ms 600 KB Output is correct
79 Correct 6 ms 604 KB Output is correct
80 Correct 6 ms 440 KB Output is correct
81 Correct 7 ms 600 KB Output is correct
82 Correct 6 ms 344 KB Output is correct