Submission #89693

#	Time	Username	Problem	Language	Result	Execution time	Memory
89693		vex	Karte (COCI18_karte)	C++14	120 / 120	93 ms	12044 KiB

karte

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12