Submission #1027552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1027552	2024-07-19T07:28:42 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++14	85 / 100	355 ms	35036 KB

jobs

#include <bits/stdc++.h>

using namespace std;
long long n,m,d;
const long long MAX=1e5+10;
pair<long long,long long> niza[MAX*10];
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()
{
    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=INT_MAX;
    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

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	6408 KB	Output is correct
2	Correct	29 ms	6484 KB	Output is correct
3	Correct	33 ms	6488 KB	Output is correct
4	Correct	29 ms	6488 KB	Output is correct
5	Correct	29 ms	6480 KB	Output is correct
6	Correct	29 ms	6484 KB	Output is correct
7	Correct	39 ms	6484 KB	Output is correct
8	Correct	29 ms	6348 KB	Output is correct
9	Correct	123 ms	6736 KB	Output is correct
10	Correct	120 ms	6492 KB	Output is correct
11	Correct	28 ms	6616 KB	Output is correct
12	Correct	56 ms	10832 KB	Output is correct
13	Correct	96 ms	15732 KB	Output is correct
14	Correct	130 ms	20568 KB	Output is correct
15	Correct	135 ms	20044 KB	Output is correct
16	Correct	194 ms	24916 KB	Output is correct
17	Correct	239 ms	32696 KB	Output is correct
18	Runtime error	238 ms	33616 KB	Memory limit exceeded
19	Runtime error	355 ms	35036 KB	Memory limit exceeded
20	Runtime error	215 ms	33104 KB	Memory limit exceeded