Submission #365401

#	Time	Username	Problem	Language	Result	Execution time	Memory
365401		lookcook	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	407 ms	116028 KiB

zalmoxis

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 2000005;
vector<int> vec[maxn];
int id[maxn];
int g = 0;

pair<int,int> comb(pair<int,int> a, pair<int,int> &b) {
    vec[a.second].push_back(b.second);
    a.first++;
    return a;
}

vector<int> res;
void dfs(int u) {
    res.push_back(id[u]);
    for (int v : vec[u]) dfs(v);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<pair<int,int>> v;
    vector<int> ori;
    int mini = 1e9;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        id[g] = x;
        v.push_back({x,g});
        g++;
        ori.push_back(x);
        mini = min(mini,x);
    }
    for (int i = mini; i <= 29; i++) {
        vector<pair<int,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--;
                    pair<int,int> p = {i,g};
                    id[g] = i;
                    g++;
                    to[to.size()-1] = comb(to[to.size()-1], p);
                    to.push_back(v[j]);
                }
            } else {
                to.push_back(v[j]);
            }
        }
        if (to[to.size()-1].first == i) {
            k--;
            pair<int,int> p = {i,g};
            id[g] = i;
            g++;
            to[to.size()-1] = comb(to[to.size()-1], p);
        }
        v = to;
    }
    assert(k>=0 && v.size() == 1 && v[0].first == 30);
    dfs(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:43:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int j = 0; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
zalmoxis.cpp:72: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]
   72 |         for (int i = 0; i < res.size(); i++) {
      |                         ~~^~~~~~~~~~~~
zalmoxis.cpp:73: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]
   73 |             if (ori.size()<=i || ori[i] != res[i]) {
      |                 ~~~~~~~~~~^~~
zalmoxis.cpp:79: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]
   79 |     for (int i = 0; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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