oj.uz

Submission #680662

# Submission time Handle Problem Language Result Execution time Memory
680662 2023-01-11T13:06:58 Z Duy_e Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 1000 ms 120804 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) {
    queue <int> q;
    q.push(v);
 
    while (q.size() < k && q.front() > 0) {
        int v = q.front(); q.pop();
        q.push(v - 1);
        q.push(v - 1);
    }
    k -= q.size();
    while (q.size()) cout << q.front() << ' ', q.pop();
 
}
 
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 --;
                    cnt ++;
                    if (k == 0) break;
                }
            }
            if (k == 0) break;
        }
        if (k == 0) break;
        b = v;
    }
 
    k += cnt;
    rep(i, 1, n) {
        cout << a[i] << ' ';
        for (int v: d[i]) {
            write(v);
        }
    }
 
 
 
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'void write(int)':
zalmoxis.cpp:17:21: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   17 |     while (q.size() < k && q.front() > 0) {
      |            ~~~~~~~~~^~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:39: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]
   39 |         for (int id = 0; id < b.size(); id ++) {
      |                          ~~~^~~~~~~~~~
zalmoxis.cpp:43: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]
   43 |                 if (id + 1 < b.size() && b[id + 1].st == val)
      |                     ~~~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 102096 KB Output is correct
2 Correct 304 ms 102656 KB Output is correct
3 Correct 277 ms 102332 KB Output is correct
4 Correct 266 ms 102528 KB Output is correct
5 Correct 273 ms 102576 KB Output is correct
6 Correct 255 ms 101676 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 539 ms 102212 KB Expected EOF
2 Incorrect 322 ms 101756 KB Expected EOF
3 Incorrect 357 ms 102564 KB Expected EOF
4 Incorrect 868 ms 108384 KB Expected EOF
5 Incorrect 357 ms 102424 KB Expected EOF
6 Incorrect 462 ms 102252 KB Expected EOF
7 Incorrect 638 ms 102524 KB Expected EOF
8 Incorrect 254 ms 102868 KB Expected EOF
9 Execution timed out 1096 ms 120804 KB Time limit exceeded
10 Execution timed out 1056 ms 93916 KB Time limit exceeded
11 Execution timed out 1091 ms 100544 KB Time limit exceeded
12 Execution timed out 1066 ms 109684 KB Time limit exceeded
13 Execution timed out 1085 ms 110364 KB Time limit exceeded
14 Execution timed out 1097 ms 109944 KB Time limit exceeded