Submission #839861

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
839861	2023-08-30T19:08:00 Z	tamionv	Longest Trip (IOI23_longesttrip)	C++17	Compilation error	0 ms	0 KB

longesttrip

#include "longesttrip.h"

#include <iostream>
#include <random>
#include <utility>

using namespace std;

mt19937 mt(123);

bool my_are_connected(vector<int> a, vector<int> b) {
    a.erase(unique(begin(a), end(a)), end(a));
    b.erase(unique(begin(b), end(b)), end(b));
    return are_connected(a, b);
}

pair<int, int> cbin(vector<int> as, vector<int> bs) {
    shuffle(begin(as), end(as), mt);
    shuffle(begin(bs), end(bs), mt);

    bool swp = false;

    if (as.size() > bs.size()) {
        swap(as, bs);
        swp = true;
    }
    pair<int, int> ret;

    if (bs.size() == 1)
        ret = make_pair(as[0], bs[0]);
    else {
        vector<int> xs(begin(bs), begin(bs) + bs.size() / 2), ys(begin(bs) + bs.size() / 2, end(bs));

        if (my_are_connected(as, xs))
            ret = cbin(as, xs);
        else
            ret = cbin(as, ys);
    }

    if (swp) swap(ret.first, ret.second);
    return ret;
}

std::vector<int> longest_trip(int N, int D) {
    mt = mt19937(123 + N + D);
    vector<int> perm(N);
    iota(begin(perm), end(perm), 0);
    shuffle(begin(perm), end(perm), mt);

    vector<int> xs = {}, ys = {};

    for (auto x : perm) {
        if (xs.empty())
            xs.push_back(x);
        else if (ys.empty()) {
            if (my_are_connected({x}, {xs.back()}))
                xs.push_back(x);
            else
                ys.push_back(x);
        } else {
            if (bernoulli_distribution(0.5)(mt)) {
                if (!my_are_connected({x}, {xs.back()}))
                    ys.push_back(x);
                else if (!my_are_connected({x}, {ys.back()}))
                    xs.push_back(x);
                else {
                    xs.push_back(x);
                    xs.insert(end(xs), begin(ys), end(ys));
                    ys = {};
                }
            } else {
                if (!my_are_connected({x}, {ys.back()}))
                    xs.push_back(x);
                else if (!my_are_connected({x}, {xs.back()}))
                    ys.push_back(x);
                else {
                    xs.push_back(x);
                    xs.insert(end(xs), begin(ys), end(ys));
                    ys = {};
                }
            }
        }
    }

    vector<int> ret = {};
    if (ys.empty())
        ret = xs;
    else {
        if (!my_are_connected(xs, ys))
            ret = (xs.size() < ys.size() ? ys : xs);
        else if (my_are_connected({xs.front(), xs.back()}, {ys.front(), ys.back()})) {
            auto [x, y] = cbin({xs.front(), xs.back()}, {ys.front(), ys.back()});
            if (xs.back() != x) reverse(begin(xs), end(xs));
            if (ys.front() != y) reverse(begin(ys), end(ys));
            xs.insert(end(xs), begin(ys), end(ys));
            ret = xs;
        } else {
            auto [x, y] = cbin(xs, ys);
            rotate(begin(xs), find(begin(xs), end(xs), x), end(xs));
            rotate(begin(ys), find(begin(ys), end(ys), y), end(ys));
            reverse(begin(xs), end(xs));
            xs.insert(end(xs), begin(ys), end(ys));
            ret = xs;
        }
    }

    return ret;
}

Compilation message

longesttrip.cpp: In function 'bool my_are_connected(std::vector<int>, std::vector<int>)':
longesttrip.cpp:12:13: error: 'unique' was not declared in this scope
   12 |     a.erase(unique(begin(a), end(a)), end(a));
      |             ^~~~~~
longesttrip.cpp: In function 'std::pair<int, int> cbin(std::vector<int>, std::vector<int>)':
longesttrip.cpp:18:5: error: 'shuffle' was not declared in this scope
   18 |     shuffle(begin(as), end(as), mt);
      |     ^~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:48:5: error: 'shuffle' was not declared in this scope
   48 |     shuffle(begin(perm), end(perm), mt);
      |     ^~~~~~~
longesttrip.cpp:93:33: error: 'reverse' was not declared in this scope
   93 |             if (xs.back() != x) reverse(begin(xs), end(xs));
      |                                 ^~~~~~~
longesttrip.cpp:94:34: error: 'reverse' was not declared in this scope
   94 |             if (ys.front() != y) reverse(begin(ys), end(ys));
      |                                  ^~~~~~~
longesttrip.cpp:99:57: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, std::tuple_element<0, std::pair<int, int> >::type&)'
   99 |             rotate(begin(xs), find(begin(xs), end(xs), x), end(xs));
      |                                                         ^
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from longesttrip.cpp:3:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  422 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note:   template argument deduction/substitution failed:
longesttrip.cpp:99:57: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   99 |             rotate(begin(xs), find(begin(xs), end(xs), x), end(xs));
      |                                                         ^
longesttrip.cpp:99:13: error: 'rotate' was not declared in this scope
   99 |             rotate(begin(xs), find(begin(xs), end(xs), x), end(xs));
      |             ^~~~~~
longesttrip.cpp:100:57: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, std::tuple_element<1, std::pair<int, int> >::type&)'
  100 |             rotate(begin(ys), find(begin(ys), end(ys), y), end(ys));
      |                                                         ^
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from longesttrip.cpp:3:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  422 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note:   template argument deduction/substitution failed:
longesttrip.cpp:100:57: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  100 |             rotate(begin(ys), find(begin(ys), end(ys), y), end(ys));
      |                                                         ^
longesttrip.cpp:101:13: error: 'reverse' was not declared in this scope
  101 |             reverse(begin(xs), end(xs));
      |             ^~~~~~~