Submission #1027558

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1027558	2024-07-19T07:31:22 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	234 ms	31316 KB

jobs

#include <bits/stdc++.h>

using namespace std;
long long n,m,d;
const long long MAX=1e5+10;
const long long MMAX=1e6+10;
pair<long long,long long> niza[MMAX];
vector<long long> v[MAX];
bool can(long long x)
{
    if(x<=0)return false;
    if(x>=m)return true;
    long long i=0;

    for(long long day=1; day<=n; day++)
    {
        long long cnt=0;
        while(i<m)
        {
            if(niza[i].first+d<day)return false;
            else if(niza[i].first>day)break;
            cnt++;
            i++;
            if(cnt==x)break;
        }
    }
    if(i>=m)return true;
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>d>>m;
    for(long long i=0; i<m; i++)
    {
        cin>>niza[i].first;
        niza[i].second=i+1;
    }
    sort(niza,niza+m);
    long long b=0,e=m;
    long long res=m;
    while(b<=e)
    {
        long long mid=(b+e)/2;
        if(can(mid))
        {
            res=mid;
            e=mid-1;
        }
        else
        {
            b=mid+1;
        }
    }
    long long i=0;
    for(long long day=1; day<=n; day++)
    {
        long long cnt=0;
        while(i<m)
        {
            if(niza[i].first>day)break;
            v[day].push_back(niza[i].second);
            cnt++;
            i++;

            if(cnt==res)break;
        }


    }
    cout<<res<<endl;
    for(long long i=1; i<=n; i++)
    {
        for(auto x:v[i])
        {
            cout<<x<<" ";
        }
        cout<<0<<endl;
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	6240 KB	Output is correct
2	Correct	23 ms	6240 KB	Output is correct
3	Correct	22 ms	6236 KB	Output is correct
4	Correct	23 ms	6240 KB	Output is correct
5	Correct	22 ms	6240 KB	Output is correct
6	Correct	22 ms	6240 KB	Output is correct
7	Correct	22 ms	6240 KB	Output is correct
8	Correct	23 ms	6284 KB	Output is correct
9	Correct	118 ms	6280 KB	Output is correct
10	Correct	115 ms	6324 KB	Output is correct
11	Correct	20 ms	6236 KB	Output is correct
12	Correct	41 ms	9864 KB	Output is correct
13	Correct	61 ms	14676 KB	Output is correct
14	Correct	91 ms	18516 KB	Output is correct
15	Correct	98 ms	18304 KB	Output is correct
16	Correct	130 ms	22096 KB	Output is correct
17	Correct	141 ms	29576 KB	Output is correct
18	Correct	165 ms	30600 KB	Output is correct
19	Correct	234 ms	31316 KB	Output is correct
20	Correct	142 ms	29580 KB	Output is correct