oj.uz

Submission #680514

# Submission time Handle Problem Language Result Execution time Memory
680514 2023-01-11T03:55:15 Z vjudge1 Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 1000 ms 120404 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);
            break;
        }
    }



    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 233 ms 102124 KB Output is correct
2 Correct 253 ms 102624 KB Output is correct
3 Correct 256 ms 102372 KB Output is correct
4 Correct 263 ms 102492 KB Output is correct
5 Correct 258 ms 102528 KB Output is correct
6 Correct 250 ms 101780 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 435 ms 102168 KB Expected EOF
2 Incorrect 319 ms 101636 KB Expected EOF
3 Incorrect 348 ms 102608 KB Expected EOF
4 Incorrect 531 ms 102580 KB Expected EOF
5 Incorrect 384 ms 102344 KB Expected EOF
6 Incorrect 285 ms 102136 KB Expected EOF
7 Incorrect 250 ms 102464 KB Expected EOF
8 Incorrect 246 ms 102888 KB Expected EOF
9 Execution timed out 1076 ms 120404 KB Time limit exceeded
10 Execution timed out 1082 ms 94304 KB Time limit exceeded
11 Execution timed out 1093 ms 103120 KB Time limit exceeded
12 Incorrect 22 ms 47252 KB Unexpected end of file - int32 expected
13 Incorrect 27 ms 47296 KB Unexpected end of file - int32 expected
14 Incorrect 23 ms 47300 KB Unexpected end of file - int32 expected