Submission #365398

#	Time	Username	Problem	Language	Result	Execution time	Memory
365398		lookcook	Zalmoxis (BOI18_zalmoxis)	C++17	25 / 100	1107 ms	145840 KiB

zalmoxis

#include <bits/stdc++.h>

#define int long long

using namespace std;

pair<int,vector<int>> comb(pair<int,vector<int>> a, pair<int,vector<int>> &b) {
    for (int x : b.second) a.second.push_back(x);
    a.first++;
    return a;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<pair<int,vector<int>>> v;
    vector<int> ori;
    int mini = 1e9;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back({x,{x}});
        ori.push_back(x);
        mini = min(mini,x);
    }
    for (int i = mini; i <= 29; i++) {
        vector<pair<int,vector<int>>> to;
        for (int j = 0; j < v.size(); j++) {
            if (!to.empty() && to[to.size()-1].first == i) {
                if (v[j].first == i) {
                    to[to.size()-1] = comb(to[to.size()-1], v[j]);
                } else {
                    k--;
                    to[to.size()-1].first++;
                    to[to.size()-1].second.push_back(i);
                    to.push_back(v[j]);
                }
            } else {
                to.push_back(v[j]);
            }
        }
        if (to[to.size()-1].first == i) {
            k--;
            to[to.size()-1].first++;
            to[to.size()-1].second.push_back(i);
        }
        v = to;
    }
    assert(k>=0 && v.size() == 1 && v[0].first == 30);
    vector<int> res = v[0].second;
    int mark = -1;
    if (k != 0) {
        for (int i = 0; i < res.size(); i++) {
            if (ori.size()<=i || ori[i] != res[i]) {
                mark = i;
                break;
            }
        }
    }
    for (int i = 0; i < res.size(); i++) {
        if (i == mark) {
            for (int j = res[i]-1; j >= res[i]-k; j--) cout << j << ' ';
            cout << res[i]-k << ' ';
        } else {
            cout << res[i] << ' ';
        }
    }
    cout << '\n';
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:30:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j = 0; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
zalmoxis.cpp:55:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < res.size(); i++) {
      |                         ~~^~~~~~~~~~~~
zalmoxis.cpp:56:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   56 |             if (ori.size()<=i || ori[i] != res[i]) {
      |                 ~~~~~~~~~~^~~
zalmoxis.cpp:62:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 25 / 70