제출 #1302114

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

jobs

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

using namespace std;

bool func(int n,int d,int m,const vector<pair<int,int>>& id,int mid)
{
    int ptr=0;
    for(int i=0;i<n;++i)
    {
        for(int j=0;ptr<m && j<mid;++j)
        {
            if(id[ptr].first+d<i)
                return false;
            else if(id[ptr].first<=i)
                ++ptr;
        }
    }

    return true;
}

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,d,m,id,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: 100 / 100