oj.uz

Submission #1081705

# Submission time Handle Problem Language Result Execution time Memory
1081705 2024-08-30T09:28:22 Z mathematik Longest Trip (IOI23_longesttrip) C++17
5 / 100
 17 ms 600 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

deque<deque<int>> combine(deque<deque<int>> p, int a, int b) {
    deque<deque<int>> erg;
    for (int i = 0; i < p.size(); i++)
        if (i != a && i != b) erg.push_back(p[i]);
    for (int i: p[a]) p[b].push_front(i);
    erg.push_back(p[b]);
    return erg;
}

vector<int> v(deque<int> d) {
    vector<int> erg;
    for (int i: d)
        erg.push_back(i);
    return erg;
}

int search(deque<int> a, deque<int> b) {
    deque<int> l, r;
    while (a.size() > 1) {
        for (int i = 0; i < a.size(); i++)
        {
            (i % 2 ? l : r).push_back(a[i]);
        }
        a = are_connected(v(l), v(b)) ? l : r;
        l.clear(); r.clear();
    }
    return a[0];
}

void push(vector<int> v, deque<int> d, int ind) {
    for (int i = 0; i < d.size(); i++)
    {
        v.push_back(d[(ind + i) % d.size()]);
    }
}

vector<int> longest_trip(int N, int D)
{
    deque<int> unused;
    for (int i = 0; i < N; i++)
        unused.push_back(i);
    deque<deque<int>> paths;
    while (unused.size() >= 4) {
        random_shuffle(unused.begin(), unused.end());
        if (are_connected({unused[0]}, {unused[1]})) {
            paths.push_back({unused[0], unused[1]});
            for (int i = 0; i < 2; i++)
                unused.pop_front();
        } else {
            deque<int> p0{unused[0]}, p1{unused[1]};
            (are_connected({unused[0]}, {unused[2]}) ? p0 : p1).push_back(unused[2]);
            (are_connected({unused[0]}, {unused[3]}) ? p0 : p1).push_back(unused[3]);
            int u = -1;
            if (p0.size() == 1) u = unused[0]; else paths.push_back(p0);
            if (p1.size() == 1) u = unused[1]; else paths.push_back(p1);
            for (int i = 0; i < 4; i++)
                unused.pop_front();
            if (u != -1) unused.push_front(u);
        }
    }
    for (int i: unused) paths.push_back({i});
    while (paths.size() > 2) {
        random_shuffle(paths.begin(), paths.end());
        if (are_connected({paths[0].front()}, {paths[1].front()})) {
            paths = combine(paths, 0, 1);
        } else if (are_connected({paths[0].front()}, {paths[2].front()})) {
            paths = combine(paths, 0, 2);
        } else {
            paths = combine(paths, 1, 2);
        }
    }
    if (are_connected(v(paths[0]), v(paths[1]))) {
        if (are_connected({paths[0].front()}, {paths[1].front()})) {
            return v(combine({paths[0], paths[1]}, 0, 1)[0]);
        }
        if (are_connected({paths[0].front()}, {paths[1].back()})) {
            reverse(paths[1].begin(), paths[1].end());
            return v(combine({paths[0], paths[1]}, 0, 1)[0]);
        }
        if (are_connected({paths[0].back()}, {paths[1].front()})) {
            reverse(paths[0].begin(), paths[0].end());
            return v(combine({paths[0], paths[1]}, 0, 1)[0]);
        }
        int c0 = search(paths[0], paths[1]);
        int c1 = search(paths[1], paths[0]);
        vector<int> erg;
        push(erg, paths[0], c0 + 1);
        push(erg, paths[1], c1);
        return erg;
    } else {
        return v(paths[0].size() > paths[1].size() ? paths[0] : paths[1]);
    }
}

Compilation message

longesttrip.cpp: In function 'std::deque<std::deque<int> > combine(std::deque<std::deque<int> >, int, int)':
longesttrip.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i = 0; i < p.size(); i++)
      |                     ~~^~~~~~~~~~
longesttrip.cpp: In function 'int search(std::deque<int>, std::deque<int>)':
longesttrip.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i = 0; i < a.size(); i++)
      |                         ~~^~~~~~~~~~
longesttrip.cpp: In function 'void push(std::vector<int>, std::deque<int>, int)':
longesttrip.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < d.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

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

Subtask #4
0.0 / 60.0

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