oj.uz

Submission #1003396

# Submission time Handle Problem Language Result Execution time Memory
1003396 2024-06-20T09:41:17 Z AtinaR Job Scheduling (CEOI12_jobs) C++14
95 / 100
 291 ms 34640 KB 
#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++)
    {
        ress[day].clear();
        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;
            ress[day].push_back(niza[i].second);
            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;
    work(res);
    for(int 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 24 ms 5980 KB Output is correct
2 Correct 24 ms 5984 KB Output is correct
3 Correct 24 ms 5984 KB Output is correct
4 Correct 23 ms 5984 KB Output is correct
5 Correct 35 ms 5976 KB Output is correct
6 Correct 25 ms 5984 KB Output is correct
7 Correct 25 ms 6016 KB Output is correct
8 Correct 25 ms 5980 KB Output is correct
9 Correct 109 ms 6380 KB Output is correct
10 Correct 113 ms 6416 KB Output is correct
11 Correct 22 ms 6236 KB Output is correct
12 Correct 47 ms 10020 KB Output is correct
13 Correct 68 ms 14420 KB Output is correct
14 Correct 98 ms 18772 KB Output is correct
15 Correct 130 ms 21484 KB Output is correct
16 Correct 128 ms 25680 KB Output is correct
17 Correct 159 ms 32648 KB Output is correct
18 Correct 175 ms 31824 KB Output is correct
19 Runtime error 291 ms 34640 KB Memory limit exceeded
20 Correct 168 ms 32596 KB Output is correct