Submission #390251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390251	2021-04-15T16:03:56 Z	grobar	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	451 ms	17444 KB

jobs

#include <bits/stdc++.h>

using namespace std;
int n,d,m;
int a[1000006];
vector< pair<int,int> >par;
bool works(int x)
{
    int curr=0;
    for(int day=0;day<n;day++)
    {
        for(int j=0;j<x;j++)
        {
            if(curr<m && par[curr].first<=day+1 && par[curr].first>=day+1-d)
            {
                curr++;
            }else
            {
                break;
            }
        }
    }
    if(curr==m)
    {
        return true;
    }else
    {
        return false;
    }
}
int main()
{
    cin>>n>>d>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a[i];
        par.push_back(make_pair(a[i],i+1));
    }
    sort(par.begin(),par.end());
    int low=0,high=m,mid,ans=-1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(works(mid)==true)
        {
            ans=mid;
            high=mid-1;
        }else
        {
            low=mid+1;
        }
    }
    cout<<ans<<endl;
    int cur = 0;
	for(int day=0;day<n;day++) {
        for(int i=0;i<ans;i++) {
            if(cur<m && par[cur].first<=day+1 && par[cur].first+d>=day+1) {
                printf("%d ",par[cur].second);
                cur++;
            }
            else break;
        }
        printf("0\n");
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	2100 KB	Output is correct
2	Correct	41 ms	2136 KB	Output is correct
3	Correct	36 ms	2160 KB	Output is correct
4	Correct	39 ms	2256 KB	Output is correct
5	Correct	43 ms	2132 KB	Output is correct
6	Correct	36 ms	2128 KB	Output is correct
7	Correct	36 ms	2112 KB	Output is correct
8	Correct	36 ms	2168 KB	Output is correct
9	Correct	48 ms	2368 KB	Output is correct
10	Correct	49 ms	2336 KB	Output is correct
11	Correct	47 ms	2116 KB	Output is correct
12	Correct	96 ms	4036 KB	Output is correct
13	Correct	144 ms	5856 KB	Output is correct
14	Correct	206 ms	7848 KB	Output is correct
15	Correct	250 ms	9736 KB	Output is correct
16	Correct	310 ms	11548 KB	Output is correct
17	Correct	363 ms	13468 KB	Output is correct
18	Correct	392 ms	15528 KB	Output is correct
19	Correct	451 ms	17444 KB	Output is correct
20	Correct	369 ms	13468 KB	Output is correct