Submission #1003379

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003379	2024-06-20T09:28:45 Z	AtinaR	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	251 ms	34384 KB

jobs

#include <bits/stdc++.h>

using namespace std;
const int MAX=1e6+10;
const int N=1e5+10;
pair<long long,long long> niza[MAX];
long long n,d,m;
vector<long long> ress[N];
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+1,i=0;
    bool flag=true;
    long long res=0;
    while(b<=e)
    {
        long long mid=(b+e)/2;
        if(mid==0)
        {
            b=mid+1;
            continue;
        }
        i=0;
        flag=true;
        for(int day=1; day<=n; day++)
        {
            for(int j=0; j<mid; j++)
            {
                if(i>=m)break;
                if(niza[i].first>day)break;
                if(niza[i].first+d<day)
                {
                    flag=false;
                    break;
                }
                i++;
            }
            if(!flag)break;
        }
        if(flag)
        {
            res=mid;
            e=mid-1;
        }
        else b=mid+1;
    }
    cout<<res<<endl;
    i=0;
    for(int day=1; day<=n; day++)
    {
        for(int j=0; j<res; j++)
        {
            if(i>=m)break;
            if(niza[i].first>day)break;
            ress[day].push_back(niza[i].second);
            i++;
        }
    }
    for(long long i=1; i<=n; i++)
    {
        for(auto x:ress[i])cout<<x<<" ";
        cout<<0<<endl;
    }
    return 0;
}
/*

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	5980 KB	Output is correct
2	Correct	23 ms	5984 KB	Output is correct
3	Correct	24 ms	5980 KB	Output is correct
4	Correct	27 ms	5972 KB	Output is correct
5	Correct	21 ms	5984 KB	Output is correct
6	Correct	21 ms	6016 KB	Output is correct
7	Correct	24 ms	5980 KB	Output is correct
8	Correct	22 ms	6160 KB	Output is correct
9	Correct	102 ms	6228 KB	Output is correct
10	Correct	110 ms	6208 KB	Output is correct
11	Correct	21 ms	6232 KB	Output is correct
12	Correct	40 ms	9872 KB	Output is correct
13	Correct	57 ms	14524 KB	Output is correct
14	Correct	85 ms	18648 KB	Output is correct
15	Correct	94 ms	19796 KB	Output is correct
16	Correct	140 ms	23888 KB	Output is correct
17	Correct	137 ms	31472 KB	Output is correct
18	Correct	175 ms	31568 KB	Output is correct
19	Runtime error	251 ms	34384 KB	Memory limit exceeded
20	Correct	144 ms	31412 KB	Output is correct