Submission #1085426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085426	2024-09-08T08:41:13 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	305 ms	34640 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

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	5984 KB	Output is correct
2	Correct	23 ms	5984 KB	Output is correct
3	Correct	23 ms	5984 KB	Output is correct
4	Correct	23 ms	6200 KB	Output is correct
5	Correct	23 ms	5984 KB	Output is correct
6	Correct	23 ms	5980 KB	Output is correct
7	Correct	26 ms	5980 KB	Output is correct
8	Correct	25 ms	6140 KB	Output is correct
9	Correct	120 ms	6228 KB	Output is correct
10	Correct	129 ms	6232 KB	Output is correct
11	Correct	21 ms	6156 KB	Output is correct
12	Correct	46 ms	9768 KB	Output is correct
13	Correct	78 ms	14420 KB	Output is correct
14	Correct	93 ms	18640 KB	Output is correct
15	Correct	101 ms	19796 KB	Output is correct
16	Correct	145 ms	24264 KB	Output is correct
17	Correct	170 ms	31688 KB	Output is correct
18	Correct	194 ms	31828 KB	Output is correct
19	Runtime error	305 ms	34640 KB	Memory limit exceeded
20	Correct	165 ms	31824 KB	Output is correct