oj.uz

Submission #423575

# Submission time Handle Problem Language Result Execution time Memory
423575 2021-06-11T09:40:43 Z egekabas Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 259 ms 47736 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int a[1000009];
int go[2000009][2];
int prt[2000009];
int val[2000009];
int cur = 1;
int last = 1;
int n, k;
int extra = 0;
void print(int v){
    if(v == 0 || extra == 0){
        cout << v << ' ';
        return;
    }
    --extra;
    print(v-1);
    print(v-1);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> k;
    val[cur] = 30;
    val[0] = 31;
    vector<pii> ans;
    int totcnt = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        while(a[i] >= val[cur] || go[cur][0] && go[cur][1]){
            if(!(go[cur][0] && go[cur][1])){
                ans.pb({1, val[cur]-1});
                totcnt++;
            }
            cur = prt[cur];
        }
        
        while(a[i] < val[cur]){
            int idx;
            if(go[cur][0] == 0)
                idx = 0;
            else
                idx = 1;
            ++last;
            go[cur][idx] = last;
            val[last] = val[cur]-1;
            prt[last] = cur;
            cur = last;
        }
        ans.pb({0, a[i]});
        
        if(a[i] == val[cur])
            cur = prt[cur];
        while(go[cur][0] && go[cur][1])
            cur = prt[cur];
    }
    while(cur != 0){
        if(!(go[cur][0] && go[cur][1])){
            ans.pb({1, val[cur]-1});
            totcnt++;
        }
        cur = prt[cur];
    }
    extra = k-totcnt;
    for(auto u : ans){
        if(u.ff == 0){
            cout << u.ss << ' ';
            continue;
        }
        print(u.ss);
    }
    
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:46:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |         while(a[i] >= val[cur] || go[cur][0] && go[cur][1]){
      |                                   ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 47580 KB Output is correct
2 Correct 217 ms 47528 KB Output is correct
3 Correct 230 ms 47620 KB Output is correct
4 Correct 216 ms 47736 KB Output is correct
5 Correct 213 ms 47540 KB Output is correct
6 Correct 219 ms 47524 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 47636 KB Output is correct
2 Correct 259 ms 47540 KB Output is correct
3 Correct 234 ms 47532 KB Output is correct
4 Correct 212 ms 47652 KB Output is correct
5 Correct 211 ms 47612 KB Output is correct
6 Correct 233 ms 47564 KB Output is correct
7 Correct 210 ms 47648 KB Output is correct
8 Correct 218 ms 47624 KB Output is correct
9 Correct 197 ms 41736 KB Output is correct
10 Correct 135 ms 19120 KB Output is correct
11 Correct 162 ms 28748 KB Output is correct
12 Correct 95 ms 2316 KB Output is correct
13 Correct 94 ms 2284 KB Output is correct
14 Correct 97 ms 2220 KB Output is correct