oj.uz

Submission #379176

# Submission time Handle Problem Language Result Execution time Memory
379176 2021-03-17T12:40:22 Z bibabas Drvca (COCI19_drvca) C++14
30 / 110
 48 ms 7656 KB 
// #define _FORTIFY_SOURCE 0 
// #pragma GCC optimize("Ofast") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("unroll-loops") 
// //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") 
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
// #pragma GCC optimize("inline") 
// #pragma GCC optimize("-fgcse") 
// #pragma GCC optimize("-fgcse-lm") 
// #pragma GCC optimize("-fipa-sra") 
// #pragma GCC optimize("-ftree-pre") 
// #pragma GCC optimize("-ftree-vrp") 
// #pragma GCC optimize("-fpeephole2") 
// #pragma GCC optimize("-ffast-math") 
// #pragma GCC optimize("-fsched-spec") 
// #pragma GCC optimize("unroll-loops") 
// #pragma GCC optimize("-falign-jumps") 
// #pragma GCC optimize("-falign-loops") 
// #pragma GCC optimize("-falign-labels") 
// #pragma GCC optimize("-fdevirtualize") 
// #pragma GCC optimize("-fcaller-saves") 
// #pragma GCC optimize("-fcrossjumping") 
// #pragma GCC optimize("-fthread-jumps") 
// #pragma GCC optimize("-funroll-loops") 
// #pragma GCC optimize("-fwhole-program") 
// #pragma GCC optimize("-freorder-blocks") 
// #pragma GCC optimize("-fschedule-insns") 
// #pragma GCC optimize("inline-functions") 
// #pragma GCC optimize("-ftree-tail-merge") 
// #pragma GCC optimize("-fschedule-insns2") 
// #pragma GCC optimize("-fstrict-aliasing") 
// #pragma GCC optimize("-fstrict-overflow") 
// #pragma GCC optimize("-falign-functions") 
// #pragma GCC optimize("-fcse-skip-blocks") 
// #pragma GCC optimize("-fcse-follow-jumps") 
// #pragma GCC optimize("-fsched-interblock") 
// #pragma GCC optimize("-fpartial-inlining") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("-freorder-functions") 
// #pragma GCC optimize("-findirect-inlining") 
// #pragma GCC optimize("-fhoist-adjacent-loads") 
// #pragma GCC optimize("-frerun-cse-after-loop") 
// #pragma GCC optimize("inline-small-functions") 
// #pragma GCC optimize("-finline-small-functions") 
// #pragma GCC optimize("-ftree-switch-conversion") 
// #pragma GCC optimize("-foptimize-sibling-calls") 
// #pragma GCC optimize("-fexpensive-optimizations") 
// #pragma GCC optimize("-funsafe-loop-optimizations") 
// #pragma GCC optimize("inline-functions-called-once") 
// #pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

using namespace std;
         
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
#define base complex<ld>
 
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)1e18;
const ld eps = (ld)1e-12;
const ll mod = (ll)1e9 + 7;
const ll p = 31;
const ll mod2 = (ll)1e9 + 7;
const ll MAXN = (ll)1000 + 3;
const ll MAXC = (ll)1e6 + 11;
const ll MAXE = (ll)100;
const ll MAXLOG = (ll)19;
const ll asci = (ll)256;
const ll block = 31623;
const ld PI = acos(-1LL);
const ld e = 2.7182818284;
         
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<
// pii,
// null_type,
// less<pii>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

ll int_rand() {
    if (RAND_MAX == (1LL << 15) - 1LL) {
        return (rand() << 15) + rand();
    }
    return rand();
}

ll ll_rand() {
    return ((ll)int_rand() << 30LL) + int_rand();
}

istream& operator >>(istream &in, pii &x) {
    cin >> x.first >> x.second;
    return in;
}
         
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
}

struct node{
    node *L = nullptr, *R = nullptr;
    int x = 0;
    bool equal = false;
    node(int x): x(x) {}
};

int set_dif(node *v) {
    int dif = -v->equal;
    if (!v->R || !v->R->R) {
        v->equal = 0;
        return dif;
    }
    if (v->R->x - v->x == v->R->R->x - v->R->x) {
        v->equal = 1;
        dif++;
    } else v->equal = 0;
    return dif;
}

int del(node *v) {
    int dif = -v->equal;
    if (v->L) v->L->R = v->R;
    if (v->R) v->R->L = v->L;
    if (v->L) dif += set_dif(v->L);
    if (v->L && v->L->L) dif += set_dif(v->L->L);
    return dif; 
}

pair<vi, vi> find(vi &a, int p1, int p2) {
    int n = a.size();
    vi used(n);
    vector<node*> list(n);
    int cnt = 0, dif = a[p2] - a[p1];
    used[p1] = 1, used[p2] = 1;
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        list[i] = new node(a[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        for (int j = i + 1; j < n; ++j) {
            if (!used[j]) {
                list[i]->R = list[j];
                break;
            }
        }
        for (int j = i - 1; j > -1; --j) {
            if (!used[j]) {
                list[i]->L = list[j];
                break;
            }
            
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) cnt += set_dif(list[i]);
    }
    int last = p2, nw = p2;
    vi f, s;
    f.push_back(a[p1]);
    f.push_back(a[p2]);
    while (last < n) {
        if (cnt >= n - f.size() - 2) {
            for (int i = 0; i < n; ++i) {
                if (!used[i]) s.push_back(a[i]);
            }
            return mp(f, s);
        }
        while (nw < n && a[last] + dif > a[nw]) ++nw;
        if (a[nw] > a[last] + dif) break;
        last = nw;
        used[last] = 1;
        cnt += del(list[last]);
        f.push_back(a[last]);
    }
    return {{}, {}};
}

void solve() {
    int n; cin >> n;
    vi a(n); cin >> a;
    sort(all(a));
    if (n == 2) {
        cout << "1\n" << a[0] << "\n1\n" << a[1];
        return;
    }
    for (int i = 0; i < 2; ++i) {
        for (int j = i + 1; j < 3; ++j) {
            auto ans = find(a, i, j);
            if (!ans.first.size()) continue;
            cout << ans.first.size() << "\n";
            for (int i : ans.first) cout << i << " ";
            cout << "\n";
            cout << ans.second.size() << "\n";
            for (int i : ans.second) cout << i << " ";
            return;
        }
    }
    cout << "-1\n";
}

signed main() {
    srand(time(0LL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); 
#endif
    cout.precision(30);
    
    solve();

    return 0LL;
}

Compilation message

drvca.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > find(std::vector<long long int>&, int, int)':
drvca.cpp:183:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         if (cnt >= n - f.size() - 2) {
      |             ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Runtime error 1 ms 492 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Runtime error 1 ms 492 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7528 KB Output is correct
2 Correct 38 ms 7528 KB Output is correct
3 Correct 48 ms 7528 KB Output is correct
4 Correct 44 ms 7528 KB Output is correct
5 Correct 39 ms 7528 KB Output is correct
6 Correct 38 ms 7528 KB Output is correct
7 Correct 38 ms 7528 KB Output is correct
8 Correct 39 ms 7528 KB Output is correct
9 Correct 45 ms 7656 KB Output is correct
10 Correct 48 ms 7528 KB Output is correct
11 Correct 31 ms 7464 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Runtime error 1 ms 492 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -