Submission #1003390

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003390	2024-06-20T09:36:43 Z	AtinaR	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	265 ms	34640 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,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;
        }
        else if(mid>=m)
        {
            res=mid;
            e=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;
        }
        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	21 ms	5980 KB	Output is correct
2	Correct	21 ms	5980 KB	Output is correct
3	Correct	22 ms	5984 KB	Output is correct
4	Correct	23 ms	5980 KB	Output is correct
5	Correct	22 ms	5980 KB	Output is correct
6	Correct	22 ms	6128 KB	Output is correct
7	Correct	21 ms	6012 KB	Output is correct
8	Correct	20 ms	5984 KB	Output is correct
9	Correct	107 ms	6224 KB	Output is correct
10	Correct	103 ms	6224 KB	Output is correct
11	Correct	21 ms	6228 KB	Output is correct
12	Correct	41 ms	9748 KB	Output is correct
13	Correct	63 ms	14448 KB	Output is correct
14	Correct	105 ms	18664 KB	Output is correct
15	Correct	111 ms	19800 KB	Output is correct
16	Correct	130 ms	24268 KB	Output is correct
17	Correct	149 ms	31828 KB	Output is correct
18	Correct	165 ms	31824 KB	Output is correct
19	Runtime error	265 ms	34640 KB	Memory limit exceeded
20	Correct	138 ms	31824 KB	Output is correct