oj.uz

Submission #61452

# Submission time Handle Problem Language Result Execution time Memory
61452 2018-07-26T04:04:24 Z Benq Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 244 ms 18636 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,K;
vpi seq;
int need;
vi ans;

void tri(int x) {
    if (!need || x == 0) ans.pb(x);
    else {
        need --;
        tri(x-1), tri(x-1);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    vi q;
    F0R(i,N) {
        int x; cin >> x;
        while (sz(q) && x > q.back()) {
            seq.pb({q.back(),1});
            q.pb(q.back());
            while (sz(q) > 1 && q.back() == q[sz(q)-2]) q.pop_back(), q.back() ++;
        }
        q.pb(x); seq.pb({x,0});
        while (sz(q) > 1 && q.back() == q[sz(q)-2]) q.pop_back(), q.back() ++;
        /*for (auto a: q) cout << a << " ";
        cout << "\n";*/
    }
    while (q.back() != 30) {
        seq.pb({q.back(),1});
        q.pb(q.back());
        while (sz(q) > 1 && q.back() == q[sz(q)-2]) q.pop_back(), q.back() ++;
    }
    need = N+K-sz(seq);
    for (auto a: seq) {
        if (a.s == 0) ans.pb(a.f);
        else tri(a.f);
    }
    for (int i: ans) cout << i << " ";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 18260 KB Output is correct
2 Correct 217 ms 18272 KB Output is correct
3 Correct 188 ms 18352 KB Output is correct
4 Correct 213 ms 18388 KB Output is correct
5 Correct 244 ms 18532 KB Output is correct
6 Correct 223 ms 18544 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 18544 KB Output is correct
2 Correct 220 ms 18544 KB Output is correct
3 Correct 196 ms 18544 KB Output is correct
4 Correct 196 ms 18544 KB Output is correct
5 Correct 192 ms 18636 KB Output is correct
6 Correct 208 ms 18636 KB Output is correct
7 Correct 211 ms 18636 KB Output is correct
8 Correct 213 ms 18636 KB Output is correct
9 Correct 184 ms 18636 KB Output is correct
10 Correct 131 ms 18636 KB Output is correct
11 Correct 239 ms 18636 KB Output is correct
12 Correct 92 ms 18636 KB Output is correct
13 Correct 111 ms 18636 KB Output is correct
14 Correct 161 ms 18636 KB Output is correct