Submission #489191

#TimeUsernameProblemLanguageResultExecution timeMemory
489191jalsolDrvca (COCI19_drvca)C++17
0 / 110
6 ms460 KiB
// 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 // }}}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...