Submission #1081782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081782		mathematik	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	22 ms	1104 KiB

longesttrip

#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()]);
    }
}

int find(deque<int> d, int v) {
    for (int i = 0; i < d.size(); i++)
        if (d[i] == v) return i;
}

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_front(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 = find(paths[0], search(paths[0], paths[1]));
        int c1 = find(paths[1], search(paths[1], {paths[0][c0]}));
        vector<int> erg;
        push(erg, paths[0], c0 + 1);
        push(erg, paths[1], c1);
        assert(erg.size() == N);
        return erg;
    } else {
        assert(paths[0].size() + paths[1].size() == N);
        return v(paths[0].size() > paths[1].size() ? paths[0] : paths[1]);
    }
}

Compilation message (stderr)

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++)
      |                     ~~^~~~~~~~~~
longesttrip.cpp: In function 'int find(std::deque<int>, int)':
longesttrip.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < d.size(); i++)
      |                     ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from longesttrip.cpp:2:
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:99:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         assert(erg.size() == N);
      |                ~~~~~~~~~~~^~~~
longesttrip.cpp:102:50: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         assert(paths[0].size() + paths[1].size() == N);
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
longesttrip.cpp: In function 'int find(std::deque<int>, int)':
longesttrip.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

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