Submission #732185

#	Time	Username	Problem	Language	Result	Execution time	Memory
732185		LKR__enjoyer	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	468 ms	14168 KiB

jobs

#include<vector>
#include <iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<bitset>
#include<set>
#include<cstdlib>
#define f first
#define sec second
#define pb push_back
typedef long long ll;
using namespace std;
int n,d,m;
vector<pair<int,int>> arr;
int zlicz[100005];
int zlicz2[100005];
bool spr(int x)
{   for(int i=1;i<=n-d;i++)zlicz2[i]=zlicz[i];
    int curr=1;
    for(int i=1;i<=n;i++)
    {
        if(i-curr>d)return 0;
        int ile=0;
        while(ile<x&&curr<=i)
        {
            int od=min(zlicz2[curr],x-ile); ile+=od;
            zlicz2[curr]-=od; if(!zlicz2[curr])curr++;
        }
        if(curr>n-d)return 1;
    }
    return 0;
}
int bin(int lo,int hi)
{
while(lo<hi)
{
    int mid=lo+(hi-lo)/2;
    if(spr(mid))hi=mid; else lo=mid+1;
}
    return lo;
}
int main()
{ ios_base::sync_with_stdio();
    cin>>n>>d>>m;
    for(int i=0;i<m;i++)
    {int a; cin>>a; arr.pb({a,i+1}); zlicz[a]++;} sort(arr.begin(),arr.end());
    int res=bin(1,m+1);
    cout<<res<<endl;
    int curr=0;
    for(int i=1;i<=n-d;i++)
    {int licz=0;
        while(licz<res&&curr<m)
        {licz++;
            if(arr[curr].f<=i){cout<<arr[curr].sec<<' '; curr++;}
        }
        cout<<'0'<<endl;
    }
    for(int i=0;i<d;i++)cout<<'0'<<endl;

        return 0;
}

• Subtask 1: 100 / 100