Submission #1018707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018707		vjudge1	Karte (COCI18_karte)	C++17	12 / 120	83 ms	9396 KiB

karte

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int n, k, a[N], cnt[N];

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], cnt[a[i]]++;

    int sm = 0;
    for (int i = 1; i <= k; i ++)
        sm += cnt[i];

    if (sm < (n - k)){
        cout << -1 << endl;
        return 0;
    }

    int need = sm - (n - k);
    vector<int> vec;
    for (int i = N - 1; i > k; i --){
        while (cnt[i]){
            cnt[i]--;
            vec.push_back(i);
        }
    }
    need += vec.size();

    for (int i = k - 1; i > 0; i --){
        while (vec.size() < 1e9 and cnt[i]){
            cnt[i]--;
            vec.push_back(i);
        }
    }

    vector<int> real;
    for (int i = 0; i < N; i ++){
        for (int j = 0; j < cnt[i]; j ++)
            real.push_back(i);

        if (vec.empty()) continue;
        real.push_back(vec.back());
        vec.pop_back();
    }

    int lies = 0;
    for (int i = 0; i < real.size(); i ++){
        if (real[i] <= lies) continue;
        lies++;
    }

    if (lies != k){
        cout << -1 << endl;
        return 0;
    }

    for (int x : real)
        cout << x << " ";
    cout << endl;



}

Compilation message (stderr)

karte.cpp: In function 'int main()':
karte.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < real.size(); i ++){
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12