oj.uz

Submission #680687

# Submission time Handle Problem Language Result Execution time Memory
680687 2023-01-11T14:04:53 Z Duy_e Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 272 ms 73416 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 = 1e6 + 10;
int 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);

    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 --;
                    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);
    }
 
 
 
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:38: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]
   38 |         for (int id = 0; id < b.size(); id ++) {
      |                          ~~~^~~~~~~~~~
zalmoxis.cpp:42: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]
   42 |                 if (id + 1 < b.size() && b[id + 1].st == val)
      |                     ~~~~~~~^~~~~~~~~~
zalmoxis.cpp:35:9: warning: unused variable 'cnt' [-Wunused-variable]
   35 |     int cnt = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 72656 KB Output is correct
2 Correct 265 ms 73312 KB Output is correct
3 Correct 248 ms 72808 KB Output is correct
4 Correct 250 ms 72932 KB Output is correct
5 Correct 255 ms 73120 KB Output is correct
6 Correct 242 ms 72164 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 72812 KB Output is correct
2 Correct 237 ms 72172 KB Output is correct
3 Correct 249 ms 73184 KB Output is correct
4 Correct 247 ms 73144 KB Output is correct
5 Correct 245 ms 72880 KB Output is correct
6 Correct 244 ms 72748 KB Output is correct
7 Correct 252 ms 73144 KB Output is correct
8 Correct 260 ms 73416 KB Output is correct
9 Correct 220 ms 69016 KB Output is correct
10 Correct 170 ms 44492 KB Output is correct
11 Correct 177 ms 51076 KB Output is correct
12 Correct 100 ms 25892 KB Output is correct
13 Correct 95 ms 25724 KB Output is correct
14 Correct 101 ms 25696 KB Output is correct