oj.uz

Submission #89693

# Submission time Handle Problem Language Result Execution time Memory
89693 2018-12-18T06:34:30 Z vex Karte (COCI18_karte) C++14
120 / 120
 93 ms 12044 KB 
#include <bits/stdc++.h>
#define maxn 500005
#define MAX 500000
using namespace std;

int n,k;
int cnt[maxn]={0};
vector<int>sol;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        cnt[x]++;
    }

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

    if(brv>k)
    {
        cout<<"-1"<<endl;
        return 0;
    }

    int br=0;
    for(int i=0;i<=k && br+brv<k;i++)
    {
        int d=min(min(cnt[i],i-br),k-br-brv);

        br+=d;
        cnt[i]-=d;
        for(int j=0;j<d;j++)sol.push_back(i);
    }
    br+=brv;

    if(br<k)
    {
        cout<<"-1"<<endl;
        return 0;
    }

    for(int i=k+1;i<=MAX;i++)
        for(int j=0;j<cnt[i];j++)sol.push_back(i);

    for(int i=0;i<=k;i++)
        for(int j=0;j<cnt[i];j++)sol.push_back(i);

    for(int i=n-1;i>=0;i--)cout<<sol[i]<<" ";
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 648 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 648 KB Output is correct
2 Correct 3 ms 688 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 712 KB Output is correct
2 Correct 3 ms 720 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 744 KB Output is correct
2 Correct 3 ms 884 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 884 KB Output is correct
2 Correct 3 ms 884 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2488 KB Output is correct
2 Correct 13 ms 2488 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5256 KB Output is correct
2 Correct 21 ms 5256 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12044 KB Output is correct
2 Correct 52 ms 12044 KB Output is correct