oj.uz

Submission #1018709

# Submission time Handle Problem Language Result Execution time Memory
1018709 2024-07-10T08:46:10 Z vjudge1 Karte (COCI18_karte) C++17
12 / 120
 82 ms 9408 KB 
#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];


    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

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 9408 KB Output isn't correct
2 Halted 0 ms 0 KB -