제출 #1302110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302110		dru-_-	Job Scheduling (CEOI12_jobs)	C++20	40 / 100	166 ms	14268 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool func(int n,const vector<int>& cnt,int mid)
{
    int cur=0;
    for(int i=0;i<n;++i)
    {
        cur+=cnt[i];
        cur-=(cur<mid?cur:mid);
    }

    return cur==0;
}

int main()
{
    std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

    int n,d,m;
    cin>>n>>d>>m;

    vector<int> cnt(n);
    vector<pair<int,int>> id(m);

    for(int i=0;i<m;++i)
    {
        int t;
        cin>>t;
        --t;

        ++cnt[t];
        id[i]={t,i+1};
    }
    
    sort(id.begin(),id.end());

    int lo=0,hi=-1;
    for(int i=0;i<n;++i)
        hi=max(hi,cnt[i]);

    while(hi-lo>1)
    {
        int mid=(hi+lo)/2;

        if(func(n,cnt,mid))
            hi=mid;
        else
            lo=mid;
    }

    cout<<hi<<'\n';

    int j=0;
    for(int i=0;i<n;++i)
    {
        int lim=j+hi;
        for(;j<m && j<lim && id[j].first<=i;++j)
            cout<<id[j].second<<' ';
        cout<<0<<'\n';
    }

    return 0;
}

• Subtask 1: 40 / 100