Submission #1226107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226107		Dreamy_lovesper	Drvca (COCI19_drvca)	C++20	110 / 110	130 ms	11972 KiB

drvca

#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first 
#define se second 
#define all(c) c.begin(), c.end()
#define pb push_back
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X &x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 100'007
ll n, g[mxn];

namespace Love1 {
    bool check () {
        return (n <= 15);
    }

    bool chk (vll&a) {
        if(a.size() == 1) return 1;
        ll diff = a[1] - a[0];
        fu(i, 1, a.size() - 1) if(a[i] - a[i - 1] != diff) return 0;
        return 1;
    }

    void DreamyLove () {
        vll ans1, ans2;

        fu(msk, 1, (1 << n) - 2) {
            vll a, b;
            fu(j, 0, n - 1) {
                if(Bitc(msk, j)) a.pb(g[j + 1]);
                else b.pb(g[j + 1]);
            }
            sort(all(a)); sort(all(b));
            if(chk(a) && chk(b)) {
                cout << a.size() << '\n';
                for(auto&i: a) cout << i << ' ';
                cout << '\n';
                cout << b.size() << '\n';
                for(auto&i: b) cout << i << ' ';
                return;
            }
        }

        cout << -1;
        //
    }
}

namespace LoveLast {

    ll o = 0;


    bool get(ll a, ll b) {
        multiset<ll> s, diff;
        fu(i, 1, n) s.insert(g[i]);
        s.erase(s.find(a));
        s.erase(s.find(b));
        ll last = -1;
        for (auto&i : s) {
            if (last != -1) diff.insert(i - last);
            last = i;
        }

        ll d = b - a;
        vll row1;
        row1.pb(a); row1.pb(b);

        while(!s.empty()) {
            if(*diff.begin() == *diff.rbegin()) {
                o = 1;
                cout << row1.size() << '\n';
                for(auto&i: row1) cout << i << ' ';
                cout << '\n';
                cout << s.size() << '\n';
                for(auto&i: s) cout << i << ' ';
                exit(0);
                return 1;
            }

            b += d;
            auto it = s.find(b);
            if(it == s.end()) return 0;
            auto l = it, r = it;
            if(it != s.begin()) {
                l--;
                diff.erase(diff.find(*it - *l));
            } 

            r++;
            if(r != s.end()) {
                diff.erase(diff.find(*r - *it));
                if (it != s.begin())  diff.insert(*r - *l);
            } 

            s.erase(it);
            row1.pb(b);
        }

    }

    void DreamyLove () {

        sort(g + 1, g + 1 + n);
        
        o |= get(g[1], g[2]);
        o |= get(g[1], g[3]);
        o |= get(g[2], g[3]);

        return void (cout << -1);        
        //
    }
}

void lovesper(const ll &TestCase) {
    
    cin >> n;
    fu(i, 1, n) cin >> g[i];

    if(Love1::check()) {
        Love1::DreamyLove();
        return;
    }


    LoveLast::DreamyLove();

}

signed main() {
    LIFESUCK

    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    
    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'bool LoveLast::get(long long int, long long int)':
drvca.cpp:150:5: warning: control reaches end of non-void function [-Wreturn-type]
  150 |     }
      |     ^

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