Submission #1085430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085430	2024-09-08T08:43:04 Z	AtinaR	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	329 ms	31212 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	23 ms	5728 KB	Output is correct
2	Correct	26 ms	5728 KB	Output is correct
3	Correct	23 ms	5728 KB	Output is correct
4	Correct	23 ms	5916 KB	Output is correct
5	Correct	23 ms	5728 KB	Output is correct
6	Correct	23 ms	5728 KB	Output is correct
7	Correct	23 ms	5728 KB	Output is correct
8	Correct	25 ms	5728 KB	Output is correct
9	Correct	131 ms	5972 KB	Output is correct
10	Correct	135 ms	5992 KB	Output is correct
11	Correct	20 ms	5720 KB	Output is correct
12	Correct	44 ms	9040 KB	Output is correct
13	Correct	67 ms	13392 KB	Output is correct
14	Correct	94 ms	16720 KB	Output is correct
15	Correct	101 ms	17804 KB	Output is correct
16	Correct	144 ms	21452 KB	Output is correct
17	Correct	160 ms	28500 KB	Output is correct
18	Correct	174 ms	28848 KB	Output is correct
19	Correct	329 ms	31212 KB	Output is correct
20	Correct	157 ms	28452 KB	Output is correct