oj.uz

Submission #1077919

# Submission time Handle Problem Language Result Execution time Memory
1077919 2024-08-27T10:33:54 Z PanosPask Longest Trip (IOI23_longesttrip) C++17
5 / 100
 20 ms 440 KB 
#include "longesttrip.h"
#define pb push_back

using namespace std;

// Find the first posiion i such that v[i] is connected to i
int find_position(vector<int>& v, int i)
{
    int l = 0;
    int r = v.size();

    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (are_connected(vector<int>(v.begin(), v.begin() + mid), {i})) {
            r = mid;
        }
        else {
            l = mid;
        }
    }

    return l;
}

vector<int> longest_trip(int N, int D)
{
    vector<int> v1, v2;

    v1.push_back(0);

    for (int i = 1; i < N; i++) {
        if (are_connected(v1, {i})) {
            if (v2.size()) {
                if (are_connected(v2, {i})) {
                    int p1 = find_position(v1, i);
                    int p2 = find_position(v2, i);

                    v1.insert(v1.begin(), v1.begin() + p1 + 1, v1.end());
                    v1.erase(v1.begin() + p1 + 1, v1.end());
                    v1.pb(i);
                    v1.insert(v1.end(), v2.begin() + p2, v2.end());
                    v1.insert(v1.end(), v2.begin(), v2.begin() + p2);
                }
                else {
                    v1.pb(i);
                }
            }
            else {
                if (are_connected({v1.back()}, {i})) {
                    v1.pb(i);
                }
                else {
                    int p = find_position(v1, i);
                    if (p == 0) {
                        v1.insert(v1.begin(), i);
                    }
                    else {
                        v1.insert(v1.end(), v1.begin(), v1.begin() + p);
                        v1.erase(v1.begin(), v1.begin() + p);
                        v1.insert(v1.begin(), i);
                    }
                }
            }
        }
        else {
            v2.pb(i);
        }
    }

    if (v1.size() > v2.size()) {
        return v1;
    }
    else {
        return v2;
    }
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 12 ms 344 KB Output is correct
4 Correct 20 ms 344 KB Output is correct
5 Correct 16 ms 440 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 12 ms 344 KB Output is correct
5 Correct 16 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Incorrect 0 ms 344 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 13 ms 344 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 17 ms 344 KB Output is correct
5 Correct 16 ms 348 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Incorrect 0 ms 344 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 12 ms 344 KB Output is correct
5 Partially correct 14 ms 344 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB Incorrect
8 Halted 0 ms 0 KB -