oj.uz

Submission #145962

# Submission time Handle Problem Language Result Execution time Memory
145962 2019-08-21T13:08:47 Z Blagojce Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 408 ms 14512 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 998244853;
ld const eps = 1e-9;


bool f(pii A, pii B){
        if(A.st < B.st) return true;
        else if(A.st > B.st) return false;
        else  return A.nd > B.nd;
}
int k;
void expand(int num){
        if(num == 0){
                cout << 0 <<' ';
                return;
        }
        if(k == 0){
                cout << num <<' ';
                return;
        }
        --k;
        expand(num - 1);
        expand(num - 1);
}
int main()
{
        int n;
        cin >> n >> k;
        int a[n];
        int b[n];
        int MIN = 40;
        int nxt[n];
        fr(i, 0, n){
                cin >> a[i];
                b[i] = a[i];
                MIN = min(a[i], MIN);
                nxt[i] = i + 1;
        }
        nxt[n - 1] = n;
        vector<pii> v;
        int sz = n;
        fr(mi, MIN, 30){
                int p = 0;
                int CNT = 0;

                while(1){

                        if(p == n){
                                break;
                        }
                        if(nxt[p] == n){
                                if(a[p] == mi){
                                        v.pb({p, mi});
                                        a[p] ++;
                                }

                        }
                        else if(a[p] == mi){
                                if(a[nxt[p]] == mi){
                                        a[p] = mi + 1;
                                        nxt[p] = nxt[nxt[p]];
                                        CNT ++;
                                }
                                else{
                                        v.pb({p, mi});
                                        a[p] = mi + 1;
                                }
                        }
                        p = nxt[p];
                }
                sz -= CNT;
                p = 0;
        }

        sort(v.begin(), v.end(), f);
        int j = 0;
        k -= (int)v.size();
        fr(i, 0, n){
                while(j < v.size() && v[j].st == i){

                        expand(v[j].nd);
                        j ++;
                }
                cout << b[i] <<' ';
        }
        cout <<endl;

        return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:91:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(j < v.size() && v[j].st == i){
                       ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 14200 KB Output is correct
2 Correct 393 ms 14192 KB Output is correct
3 Correct 408 ms 14172 KB Output is correct
4 Correct 394 ms 14328 KB Output is correct
5 Correct 397 ms 14384 KB Output is correct
6 Correct 391 ms 14172 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 14228 KB Output is correct
2 Correct 392 ms 14172 KB Output is correct
3 Correct 397 ms 14212 KB Output is correct
4 Correct 395 ms 14512 KB Output is correct
5 Correct 398 ms 14196 KB Output is correct
6 Correct 394 ms 14200 KB Output is correct
7 Correct 395 ms 14292 KB Output is correct
8 Correct 405 ms 14172 KB Output is correct
9 Correct 363 ms 13044 KB Output is correct
10 Correct 215 ms 7140 KB Output is correct
11 Correct 275 ms 9660 KB Output is correct
12 Correct 101 ms 2412 KB Output is correct
13 Correct 101 ms 2296 KB Output is correct
14 Correct 100 ms 2296 KB Output is correct