답안 #365401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365401 2021-02-11T15:28:12 Z lookcook Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
407 ms 116028 KB
#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

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++) {
      |                     ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 376 ms 115660 KB Output is correct
2 Correct 386 ms 115780 KB Output is correct
3 Correct 390 ms 115856 KB Output is correct
4 Correct 407 ms 115736 KB Output is correct
5 Correct 383 ms 115688 KB Output is correct
6 Correct 373 ms 115612 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 115700 KB Output is correct
2 Correct 372 ms 116028 KB Output is correct
3 Correct 394 ms 115676 KB Output is correct
4 Correct 392 ms 115776 KB Output is correct
5 Correct 387 ms 115640 KB Output is correct
6 Correct 381 ms 115868 KB Output is correct
7 Correct 387 ms 115932 KB Output is correct
8 Correct 390 ms 115792 KB Output is correct
9 Correct 346 ms 108440 KB Output is correct
10 Correct 221 ms 78152 KB Output is correct
11 Correct 267 ms 93488 KB Output is correct
12 Correct 125 ms 55404 KB Output is correct
13 Correct 126 ms 55276 KB Output is correct
14 Correct 128 ms 55276 KB Output is correct