oj.uz

Submission #839194

# Submission time Handle Problem Language Result Execution time Memory
839194 2023-08-29T03:11:11 Z anha3k25cvp Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 475 ms 68912 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n, k;
    cin >> n >> k;
    vector <int> a(n + k + 1, 0), nex(n + 1, 0), last(n + 1, 0);
    set <II> q;
    int mi = inf;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        mi = min(mi, a[i]);
        q.insert({a[i], i});
        last[i] = i;
        if (i < n)
            nex[i] = i + 1;
    }
    int cnt = n;
    vector <int> c(n + k + 1, 0), b = a;
    while (!q.empty()) {
        int val = q.begin() -> st, u = q.begin() -> nd;
        q.erase(q.begin());
        if (val == 30)
            break;
        int v = nex[u];
        if (v && b[v] == b[u]) {
            q.erase(q.begin());
            c[last[u]] = v;
            last[u] = last[v];
            nex[u] = nex[v];
            q.insert({b[u] = val + 1, u});
        }
        else {
            a[++ cnt] = val;
            c[last[u]] = cnt;
            last[u] = cnt;
            q.insert({b[u] = val + 1, u});
        }
    }
    int pos = 1, n_ = n;
    n += k;
    for (int i = 1; i <= cnt; i ++) {
        if (pos > n_) {
            int x = n - cnt + 1, k = 0, val = 1 << a[pos];
            if (val <= x) {
                for (int j = 0; j < val; j ++)
                    cout << "0 ";
                n -= val - 1;
            }
            else {
                for (; (1 << k) < x; k ++);
                a[pos] -= k;
                int y = (1 << k) - x;
                for (int j = 1; j <= x; j ++)
                    if (j <= y)
                        cout << a[pos] + 1 << ' ';
                    else
                        cout << a[pos] << ' ';
                n = cnt;
            }
        }
        else
            cout << a[pos] << ' ';
        pos = c[pos];
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:19:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
zalmoxis.cpp:20:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 68912 KB Output is correct
2 Correct 473 ms 68912 KB Output is correct
3 Correct 459 ms 68856 KB Output is correct
4 Correct 456 ms 68904 KB Output is correct
5 Correct 464 ms 68908 KB Output is correct
6 Correct 454 ms 68840 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 68912 KB Output is correct
2 Correct 453 ms 68848 KB Output is correct
3 Correct 454 ms 68812 KB Output is correct
4 Correct 461 ms 68900 KB Output is correct
5 Correct 454 ms 68908 KB Output is correct
6 Correct 465 ms 68904 KB Output is correct
7 Correct 475 ms 68904 KB Output is correct
8 Correct 454 ms 68908 KB Output is correct
9 Correct 404 ms 58000 KB Output is correct
10 Correct 165 ms 30440 KB Output is correct
11 Correct 273 ms 41480 KB Output is correct
12 Correct 36 ms 14028 KB Output is correct
13 Correct 36 ms 14028 KB Output is correct
14 Correct 36 ms 14036 KB Output is correct