oj.uz

Submission #680690

# Submission time Handle Problem Language Result Execution time Memory
680690 2023-01-11T14:08:46 Z vjudge1 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 291 ms 73512 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 245 ms 72632 KB Output is correct
2 Correct 262 ms 73212 KB Output is correct
3 Correct 246 ms 72868 KB Output is correct
4 Correct 250 ms 72972 KB Output is correct
5 Correct 240 ms 73060 KB Output is correct
6 Correct 235 ms 72352 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 72792 KB Output is correct
2 Correct 233 ms 72192 KB Output is correct
3 Correct 291 ms 73072 KB Output is correct
4 Correct 241 ms 73208 KB Output is correct
5 Correct 261 ms 72944 KB Output is correct
6 Correct 259 ms 72764 KB Output is correct
7 Correct 240 ms 73140 KB Output is correct
8 Correct 280 ms 73512 KB Output is correct
9 Correct 206 ms 69084 KB Output is correct
10 Correct 147 ms 44448 KB Output is correct
11 Correct 171 ms 51128 KB Output is correct
12 Correct 93 ms 25700 KB Output is correct
13 Correct 94 ms 25984 KB Output is correct
14 Correct 91 ms 25772 KB Output is correct