oj.uz

Submission #680515

# Submission time Handle Problem Language Result Execution time Memory
680515 2023-01-11T04:00:21 Z vjudge1 Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 1000 ms 118032 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 255 ms 100084 KB Output is correct
2 Correct 247 ms 100632 KB Output is correct
3 Correct 280 ms 100228 KB Output is correct
4 Correct 298 ms 100440 KB Output is correct
5 Correct 265 ms 100420 KB Output is correct
6 Correct 273 ms 99580 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 522 ms 100152 KB Expected EOF
2 Incorrect 362 ms 99652 KB Expected EOF
3 Incorrect 370 ms 100524 KB Expected EOF
4 Incorrect 949 ms 106304 KB Expected EOF
5 Incorrect 374 ms 100400 KB Expected EOF
6 Incorrect 463 ms 100200 KB Expected EOF
7 Incorrect 577 ms 100504 KB Expected EOF
8 Incorrect 281 ms 100780 KB Expected EOF
9 Execution timed out 1088 ms 118032 KB Time limit exceeded
10 Execution timed out 1077 ms 93140 KB Time limit exceeded
11 Execution timed out 1086 ms 100672 KB Time limit exceeded
12 Execution timed out 1093 ms 108708 KB Time limit exceeded
13 Execution timed out 1092 ms 108868 KB Time limit exceeded
14 Execution timed out 1086 ms 108524 KB Time limit exceeded