oj.uz

Submission #1018704

# Submission time Handle Problem Language Result Execution time Memory
1018704 2024-07-10T08:43:18 Z vjudge1 Karte (COCI18_karte) C++17
0 / 120
 105 ms 10180 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];

    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 = 1; i < k; i ++){
        while (vec.size() < need 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:32:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         while (vec.size() < need and cnt[i]){
      |                ~~~~~~~~~~~^~~~~~
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
0 / 12.0

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

Subtask #2
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 #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 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 1 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 1 ms 344 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 17 ms 2264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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