Submission #1003394

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003394	2024-06-20T09:39:51 Z	AtinaR	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	261 ms	34624 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];
bool work(int mid)
{
    if(mid<=0)return false;
    if(mid>=m)return true;
    int i=0;
    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)return false;
            i++;
        }
    }
    return (i>=m);
}
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=0;
    while(b<e)
    {
        long long mid=(b+e)/2;
        bool flag=work(mid);
        if(flag)
        {
            res=mid;
            e=mid;
        }
        else b=mid+1;
    }
    cout<<res<<endl;
    int 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(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	22 ms	5984 KB	Output is correct
2	Correct	23 ms	6208 KB	Output is correct
3	Correct	26 ms	5984 KB	Output is correct
4	Correct	28 ms	5980 KB	Output is correct
5	Correct	23 ms	5980 KB	Output is correct
6	Correct	23 ms	5984 KB	Output is correct
7	Correct	21 ms	5984 KB	Output is correct
8	Correct	26 ms	5984 KB	Output is correct
9	Correct	123 ms	6228 KB	Output is correct
10	Correct	113 ms	6312 KB	Output is correct
11	Correct	18 ms	6304 KB	Output is correct
12	Correct	51 ms	9968 KB	Output is correct
13	Correct	60 ms	14420 KB	Output is correct
14	Correct	89 ms	18768 KB	Output is correct
15	Correct	94 ms	19796 KB	Output is correct
16	Correct	128 ms	24148 KB	Output is correct
17	Correct	144 ms	31824 KB	Output is correct
18	Correct	171 ms	31824 KB	Output is correct
19	Runtime error	261 ms	34624 KB	Memory limit exceeded
20	Correct	143 ms	31824 KB	Output is correct