Submission #489191

#	Time	Username	Problem	Language	Result	Execution time	Memory
489191		jalsol	Drvca (COCI19_drvca)	C++17	0 / 110	6 ms	460 KiB

drvca

// looking to shine brighter in this world...

#define TASK "empty"
#define MTC 0

#ifdef LOCAL
#include "local_header.h"
#include "debugger.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

// {{{
using namespace std;

using ll = long long; using ld = long double;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>;
using pi = pair<int, int>; using vpi = vector<pi>; using vvpi = vector<vpi>;
using pl = pair<ll, ll>; using vpl = vector<pl>; using vvpl = vector<vpl>;
using str = string; using vstr = vector<str>;
template <class T, class Cmp = less<T>> using pq = priority_queue<T, vector<T>, Cmp>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define elif else if

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class C, class T> inline bool contains(const C& c, const T& a) { return c.find(a) != c.end(); }
template <class T> inline void remdup(vector<T>& v) { sort(v); v.erase(unique(all(v)), v.end()); }

#define FNC(t, s, f) template <class C> inline t s(C& c) { return f(all(c)); }
FNC(void, sort, sort) FNC(void, rev, reverse) FNC(bool, nextperm, next_permutation) FNC(bool, prevperm, prev_permutation) FNC(bool, issorted, is_sorted)

#define FCP(t, n, d, s) template <class C, class A> inline t n##s(C& c, const A& a) { return n##d##s(all(c), a); }
FCP(bool, all, _, of) FCP(bool, any, _, of) FCP(bool, none, _, of) FCP(int, count, , ) FCP(int, count, _, if) FCP(void, shuffle, , )

#define FT(t, s, f) template <class T> inline t s(vector<T>& v, const T& init = 0) { return f(all(v), init); }
FT(void, iota, iota) FT(void, fill, fill) FT(int, totof, accumulate)
template <class T, class Cmp> inline T totof(const vector<T>& x, const T& init, Cmp op) { return accumulate(all(x), static_cast<T>(init), op); }

template <class A, class B> istream& operator>>(istream& is, pair<A, B>& p) { return is >> p.fi >> p.se; }
template <class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << p.fi << ' ' << p.se; }
template <class T> istream& operator>>(istream& is, vector<T>& v) { Fe (&x : v) is >> x; return is; }
template <class T> ostream& operator<<(ostream& os, const vector<T>& v) { if (!isz(v)) return os; Rep (i, isz(v) - 1) { os << v[i] << ' '; } return os << v.back(); }
struct Rdr { bool ok = true; explicit operator bool() { return ok; } template <class T> Rdr& operator, (T& _t_) { ok &= !!(cin >> _t_); return *this; } };
template <char S, char E> struct Wtr { bool ok = true; bool _space_; void wrCh(char c) { if (c) cout << c; } Wtr() : _space_(false) {} ~Wtr() { wrCh(E); } explicit operator bool() { return ok; } template <class T> Wtr& operator, (const T& _t_) { (_space_) ? (wrCh(S)) : (void(_space_ = true)); ok &= !!(cout << _t_); return *this; } };
#define re Rdr(),
#define pr Wtr<'\0', '\0'>(),
#define prln Wtr<'\0', '\n'>(),
#define wr Wtr<' ', ' '>(),
#define wrln Wtr<' ', '\n'>(),
#define nl cout << '\n'

mt19937_64 MtFixed(9999);
mt19937_64 Mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());
template <class T> inline T rng(T a, T b, bool fixed = false) { return uniform_int_distribution<T>(a, b)(fixed ? MtFixed : Mt); }

#define CMP(n, op) template <class T> typename vector<T>::iterator n##of(vector<T>& v) { return n##_element(all(v)); } template <class T> bool ch##n(T& a, const T& b) { return (!(a op b)) ? a = b, true : false; }
CMP(max, >=) CMP(min, <=)
#define max(...) max({__VA_ARGS__})
#define min(...) min({__VA_ARGS__})
template <class T, class F> inline T fsttrue(T lo, T hi, const F& f) { ++hi; assert(lo <= hi); while (lo < hi) { T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; }
template <class T, class F> inline T lsttrue(T lo, T hi, const F& f) { --lo; assert(lo <= hi); while (lo < hi) { T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; }
#define BND(s, l) template <class A, class B> inline int s(vector<A>& v, B& x) { return l##_bound(all(v), static_cast<A>(x)) - v.begin(); }
BND(lwb, lower) BND(upb, upper)

template <class T> inline bool gbit(T mask, int b) { return (mask >> b & T(1)); }
template <class T> inline void sbit(T& mask, int b) { mask |= (T(1) << b); }
template <class T> inline void dbit(T& mask, int b) { mask &= ~(T(1) << b); }
template <class T> inline void fbit(T& mask, int b) { mask ^= (T(1) << b); }

inline int popcnt(ll x) { return __builtin_popcountll(x); }
inline int clz(ll x) { return __builtin_clzll(x); }
inline int lg2(ll x) { return x ? 63 - clz(x) : -1; }

#if __cplusplus < 201703L
template <class T> inline T gcd(T a, T b) { while (b) { a %= b; swap(a, b); } return a; }
template <class T> inline T lcm(T a, T b) { return 1LL * a / gcd(a, b) * b; }
#endif

inline const char* YN(bool cond) { return cond ? "YES" : "NO"; }
inline const char* Yn(bool cond) { return cond ? "Yes" : "No"; }
inline const char* yn(bool cond) { return cond ? "yes" : "no"; }

#if __cplusplus >= 201402L
template <class F> struct __y_combinator_struct__ { F fun_; template <class T> explicit __y_combinator_struct__(T&& fun): fun_(forward<T>(fun)) {} template <class ...Args> decltype(auto) operator()(Args&& ...args) { return fun_(ref(*this), forward<Args>(args)...); } };
template <class F> decltype(auto) yc(F&& fun) { return __y_combinator_struct__<decay_t<F>>(forward<F>(fun)); }
#endif

struct chash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } };
template <class K, class V> using hmap = unordered_map<K, V, chash>;
template <class K> using hset = unordered_set<K, chash>;

// U UR R DR D DL L UL
constexpr pi d8[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
constexpr pi d4[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
// }}}

constexpr int maxn = 3e5 + 5;

struct Solution {
    void main() {
        int n; re n; assert(n <= 20);
        vi a(n); re a;
        sort(all(a));

        Rep (mask, (1 << n)) {
            vi sa, sb;

            Rep (i, n) {
                if (gbit(mask, i)) {
                    sa.push_back(a[i]);
                } else {
                    sb.push_back(a[i]);
                }
            }

            if (!isz(sa) || !isz(sb)) continue;

            vi diffa = sa, diffb = sb;

            adjacent_difference(all(diffa), diffa.begin());
            adjacent_difference(all(diffb), diffb.begin());

            bool ok = true;
            ok &= all_of(all(diffa), [&](int x) { return x == diffa[0]; });
            ok &= all_of(all(diffb), [&](int x) { return x == diffb[0]; });

            if (ok) {
                wrln isz(sa);
                wrln sa;
                wrln isz(sb);
                wrln sb;
                return;
            }
        }

        wrln -1;
    }
};

void init() {

}

// {{{
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }

    cout << setprecision(9) << fixed;
    init();

#if MTC == 1
    int ntc; (cin >> ntc).ignore(); Rep (itc, ntc)
#elif MTC == 2
    for (;;)
#endif
    {
#if __cplusplus >= 201402L
        make_unique<Solution>()->main();
#else
        Solution* solver = new Solution{};
        solver->main();
        delete solver;
#endif
    }

    return 0;
}
// vim: fdm=marker foldenable foldlevel=0
// }}}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30