Submission #1085431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085431	2024-09-08T08:44:32 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++14	75 / 100	285 ms	31312 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

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	5728 KB	Output is correct
2	Correct	25 ms	5728 KB	Output is correct
3	Correct	24 ms	5724 KB	Output is correct
4	Correct	27 ms	5724 KB	Output is correct
5	Correct	25 ms	5920 KB	Output is correct
6	Correct	23 ms	5724 KB	Output is correct
7	Correct	27 ms	5728 KB	Output is correct
8	Correct	30 ms	5724 KB	Output is correct
9	Correct	121 ms	5972 KB	Output is correct
10	Correct	119 ms	5968 KB	Output is correct
11	Incorrect	21 ms	5976 KB	Output isn't correct
12	Correct	43 ms	9044 KB	Output is correct
13	Incorrect	63 ms	13248 KB	Output isn't correct
14	Incorrect	97 ms	16740 KB	Output isn't correct
15	Correct	100 ms	18000 KB	Output is correct
16	Incorrect	133 ms	21328 KB	Output isn't correct
17	Correct	163 ms	28500 KB	Output is correct
18	Correct	181 ms	28756 KB	Output is correct
19	Incorrect	285 ms	31312 KB	Output isn't correct
20	Correct	159 ms	28500 KB	Output is correct