oj.uz

Submission #732181

# Submission time Handle Problem Language Result Execution time Memory
732181 2023-04-28T15:28:40 Z LKR__enjoyer Job Scheduling (CEOI12_jobs) C++17
80 / 100
 380 ms 22180 KB 
#include<vector>
#include <iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<bitset>
#include<set>
#include<cstdlib>
#define f first
#define sec second
#define pb push_back
typedef long long ll;
using namespace std;
int n,d,m;
vector<pair<int,int>> arr;
int zlicz[100001];
int zlicz2[100001];
bool spr(int x)
{   for(int i=1;i<=n-d;i++)zlicz2[i]=zlicz[i];
    int curr=1;
    for(int i=1;i<=n;i++)
    {
        if(i-curr>d)return 0;
        int ile=0;
        while(ile<x&&curr<=i)
        {
            int od=min(zlicz2[curr],x-ile); ile+=od;
            zlicz2[curr]-=od; if(!zlicz2[curr])curr++;
        }
        if(curr>n-d)return 1;
    }
    return 0;
}
int bin(int lo,int hi)
{
while(lo<hi)
{
    int mid=lo+(hi-lo)/2;
    if(spr(mid))hi=mid; else lo=mid+1;
}
    return lo;
}
int main()
{
    cin>>n>>d>>m;
    for(int i=0;i<m;i++)
    {int a; cin>>a; arr.pb({a,i+1}); zlicz[a]++;} sort(arr.begin(),arr.end());
    int res=bin(1,m);
    cout<<res<<endl;
    int curr=0;
    for(int i=1;i<=n-d;i++)
    {int licz=0;
        if(curr==m){cout<<'0'<<endl; continue;}
        while(licz<res)
        {licz++;
            if(arr[curr].f<=i){cout<<arr[curr].sec<<' '; curr++;}
        }
        cout<<'0'<<endl;
    }
    for(int i=0;i<d;i++)cout<<'0'<<endl;

        return 0;
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1864 KB Output is correct
2 Correct 43 ms 1880 KB Output is correct
3 Correct 61 ms 1852 KB Output is correct
4 Correct 43 ms 1852 KB Output is correct
5 Correct 44 ms 1868 KB Output is correct
6 Correct 42 ms 1888 KB Output is correct
7 Correct 47 ms 1808 KB Output is correct
8 Correct 53 ms 1856 KB Output is correct
9 Runtime error 43 ms 3740 KB Execution killed with signal 11
10 Runtime error 47 ms 3652 KB Execution killed with signal 11
11 Correct 40 ms 1756 KB Output is correct
12 Correct 78 ms 3208 KB Output is correct
13 Correct 116 ms 4660 KB Output is correct
14 Correct 218 ms 6052 KB Output is correct
15 Correct 192 ms 7688 KB Output is correct
16 Correct 276 ms 9324 KB Output is correct
17 Correct 315 ms 10796 KB Output is correct
18 Runtime error 376 ms 19392 KB Execution killed with signal 11
19 Runtime error 380 ms 22180 KB Execution killed with signal 11
20 Correct 318 ms 10736 KB Output is correct