Submission #841305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
841305	2023-09-01T13:24:25 Z	I_love_Hoang_Yen	Longest Trip (IOI23_longesttrip)	C++17	Compilation error	0 ms	0 KB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

// Subtask 1: D == 3
vector<int> sub1(int n) {
    vector<int> res(n);
    std::iota(res.begin(), res.end(), 0);
    return res;
}

// Subtask 2: D == 2
bool has_edge(int u, int v) {
    return are_connected({u}, {v});
}

vector<int> sub2(int n) {
    vector<int> res {0};
    for (int i = 1; i < n; i++) {
        if (has_edge(0, i)) {
            res.push_back(i);
            break;
        }
    }

    for (int i = 1; i < n; i++) {
        if (i == res[1]) continue;

        if (has_edge(res.back(), i)) {
            res.push_back(i);
        } else {
            res.insert(res.begin(), i);
        }
    }

    return res;
}

// Subtask 3: D == 1, return path with length >= Lmax / 2
vector<int> sub3(int n) {
    // maintain 2 paths
    vector<int> p1 {0}, p2 {1};

    for (int i = 2; i < n; ++i) {
        // consider p1.back(), p2.back(), i
        // -> there's at least 1 edge

        if (has_edge(p1.back(), i)) {
            p1.push_back(i);
        } else if (has_edge(p2.back(), i)) {
            p2.push_back(i);
        } else {
            reverse(p2.begin(), p2.end());
            p1.insert(p1.end(), p2.begin(), p2.end());
            p2 = {i};
        }
    }
    if (p1.size() > p2.size()) return p1;
    return p2;
}

// Subtask 4: D == 1
vector<int> sub4(int n) {
    // Use subtask 3 to get 2 paths {{{
    vector<int> p1 {0}, p2 {1};
    for (int i = 2; i < n; ++i) {
        if (has_edge(p1.back(), i)) {
            p1.push_back(i);
        } else if (has_edge(p2.back(), i)) {
            p2.push_back(i);
        } else {
            reverse(p2.begin(), p2.end());
            p1.insert(p1.end(), p2.begin(), p2.end());
            p2 = {i};
        }
    }
    // }}}
    
    // Make p1 longer path
    if (p1.size() < p2.size()) swap(p1, p2);
    if (p2.empty()) return p1;

    // Impossible to merge 2 paths
    if (!are_connected(p1, p2)) {
        return p1;
    }
    
    // Merge 2 paths:
    // Consider: p1[0], p1.back() and p2[0] -> at least 1 edge
    if (has_edge(p1.back(), p2[0])) {
        p1.insert(p1.end(), p2.begin(), p2.end());
        return p1;
    } else if (has_edge(p1[0], p2[0])) {
        reverse(p2.begin(), p2.end());
        p2.insert(p2.end(), p1.begin(), p1.end());
        return p2;
    }

    // p1 is now a circle
    // corner case: |p2| == 1
    if (p2.size() == 1) {
        for (int i = 0; i < p1.size(); ++i) {
            if (has_edge(p1[i], p2[0])) {
                reverse(p2.begin(), p2.end());
                p2.insert(p2.end(), p1.begin() + i, p1.end());
                p2.insert(p2.end(), p1.begin(), p1.begin() + i);
                return p2;
            }
        }
    }

    // Consider: p2[0], p2.back() and p1[0] -> at least 1 edge
    if (has_edge(p2[0], p1[0])) {
        reverse(p1.begin(), p1.end());
        p1.insert(p1.end(), p2.begin(), p2.end());
        return p1;
    } else if (has_edge(p2.back(), p1[0])) {
        p2.insert(p2.back(), p1.begin(), p1.end());
        return p2;
    }

    // p2 is now also a circle
    // Find one edge from p1 -> p2
    for (int i = 0; i < p1.size(); i++) {
        for (int j = 0; j < p2.size(); j++) {
            if (has_edge(p1[i], p2[j])) {
                vector<int> res;
                res.insert(res.end(), p1.begin() + i + 1, p1.end());
                res.insert(res.end(), p1.begin(), p1.begin() + i + 1);
                res.insert(res.end(), p2.begin() + j, p2.end());
                res.insert(res.end(), p2.begin(), p2.begin() + j);
                return res;
            }
        }
    }
    return p1;
}

vector<int> longest_trip(int n, int d) {
    if (d == 3) return sub1(n);
    if (d == 2) return sub2(n);
    return sub4(n);
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> sub4(int)':
longesttrip.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < p1.size(); ++i) {
      |                         ~~^~~~~~~~~~~
longesttrip.cpp:118:50: error: no matching function for call to 'std::vector<int>::insert(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, std::vector<int>::iterator, std::vector<int>::iterator)'
  118 |         p2.insert(p2.back(), p1.begin(), p1.end());
      |                                                  ^
In file included from /usr/include/c++/10/vector:72,
                 from longesttrip.h:1,
                 from longesttrip.cpp:1:
/usr/include/c++/10/bits/vector.tcc:130:5: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = std::vector<int>::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<int>::const_iterator; std::vector<_Tp, _Alloc>::value_type = int]'
  130 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:130:5: note:   candidate expects 2 arguments, 3 provided
In file included from /usr/include/c++/10/vector:67,
                 from longesttrip.h:1,
                 from longesttrip.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1293:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = std::vector<int>::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<int>::const_iterator; std::vector<_Tp, _Alloc>::value_type = int]'
 1293 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1293:7: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/10/bits/stl_vector.h:1310:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::initializer_list<_Tp>) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = std::vector<int>::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<int>::const_iterator]'
 1310 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1310:7: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/10/bits/stl_vector.h:1335:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = std::vector<int>::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<int>::const_iterator; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = int]'
 1335 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1335:29: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'std::vector<int>::const_iterator'
 1335 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |              ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1379:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = int; _Alloc = std::allocator<int>]'
 1379 |  insert(const_iterator __position, _InputIterator __first,
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1379:2: note:   template argument deduction/substitution failed:
longesttrip.cpp:118:26: note:   cannot convert 'p2.std::vector<int>::back()' (type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}) to type 'std::vector<int>::const_iterator'
  118 |         p2.insert(p2.back(), p1.begin(), p1.end());
      |                   ~~~~~~~^~
longesttrip.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < p1.size(); i++) {
      |                     ~~^~~~~~~~~~~
longesttrip.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int j = 0; j < p2.size(); j++) {
      |                         ~~^~~~~~~~~~~