oj.uz

Submission #680685

# Submission time Handle Problem Language Result Execution time Memory
680685 2023-01-11T14:01:13 Z Duy_e Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 273 ms 100808 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);

    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 233 ms 100076 KB Output is correct
2 Correct 248 ms 100604 KB Output is correct
3 Correct 265 ms 100260 KB Output is correct
4 Correct 252 ms 100412 KB Output is correct
5 Correct 273 ms 100448 KB Output is correct
6 Correct 233 ms 99624 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 100124 KB Output is correct
2 Correct 236 ms 99628 KB Output is correct
3 Correct 240 ms 100548 KB Output is correct
4 Correct 246 ms 100584 KB Output is correct
5 Correct 250 ms 100348 KB Output is correct
6 Correct 247 ms 100200 KB Output is correct
7 Correct 235 ms 100468 KB Output is correct
8 Correct 247 ms 100808 KB Output is correct
9 Correct 226 ms 95816 KB Output is correct
10 Correct 148 ms 69156 KB Output is correct
11 Correct 186 ms 76668 KB Output is correct
12 Correct 100 ms 49184 KB Output is correct
13 Correct 100 ms 49192 KB Output is correct
14 Correct 100 ms 49244 KB Output is correct