Submission #1302092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302092		dru-_-	Job Scheduling (CEOI12_jobs)	C++20	40 / 100	161 ms	14276 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].first=t;
        id[i].second=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';

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

    return 0;
}

• Subtask 1: 40 / 100