oj.uz

Submission #680683

# Submission time Handle Problem Language Result Execution time Memory
680683 2023-01-11T13:57:42 Z Duy_e Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 269 ms 100832 KB 
#include <bits/stdc++.h>
#define ll long long
#define st first
#define nd second
#define pii pair <ll, ll>
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;
const long long N = 2e6 + 10;
ll n, k, a[N], b[N], cnt;
vector <int> d[N];

void write(int v) {
    if (v == 0 || k == 0) {
        cout << v << ' ';
        return;
    }

    if (k > 0) {
        k --;
        write(v - 1);
        write(v - 1);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    // freopen("test.inp", "r", stdin);
    // freopen("test.out", "w", stdout);

    cin >> n >> k;
    vector <pii> b;
 
    rep(i, 1, n) cin >> a[i], b.push_back({a[i], i});
 
    int cnt = 0;
    rep(val, 0, 29) {
        vector <pii> v;
        for (int id = 0; id < b.size(); id ++) {
            int x = b[id].st;
            if (val != x) v.push_back(b[id]);
            else {
                if (id + 1 < b.size() && b[id + 1].st == val)
                    v.push_back({val + 1, b[id + 1].nd}), id ++;
                else {
                    d[b[id].nd].push_back(val);
                    v.push_back({val + 1, b[id].nd});
                    k --;
                    cnt ++;
                    if (k == 0) break;
                }
            }
            if (k == 0) break;
        }
        if (k == 0) break;
        b = v;
    }
 
    rep(i, 1, n) {
        cout << a[i] << ' ';
        for (int v: d[i]) {
            write(v);
            // cout << v << ' ';
        }
    }
 
 
 
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:41:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int id = 0; id < b.size(); id ++) {
      |                          ~~~^~~~~~~~~~
zalmoxis.cpp:45:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 if (id + 1 < b.size() && b[id + 1].st == val)
      |                     ~~~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 100084 KB Output is correct
2 Correct 248 ms 100608 KB Output is correct
3 Correct 245 ms 100284 KB Output is correct
4 Correct 241 ms 100344 KB Output is correct
5 Correct 238 ms 100488 KB Output is correct
6 Correct 246 ms 99648 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 100204 KB Output is correct
2 Correct 231 ms 99612 KB Output is correct
3 Correct 244 ms 100568 KB Output is correct
4 Correct 245 ms 100576 KB Output is correct
5 Correct 266 ms 100404 KB Output is correct
6 Correct 269 ms 100176 KB Output is correct
7 Correct 263 ms 100492 KB Output is correct
8 Correct 260 ms 100832 KB Output is correct
9 Correct 217 ms 95688 KB Output is correct
10 Correct 156 ms 69128 KB Output is correct
11 Correct 184 ms 76472 KB Output is correct
12 Correct 112 ms 49224 KB Output is correct
13 Correct 100 ms 49232 KB Output is correct
14 Correct 116 ms 49236 KB Output is correct