oj.uz

Submission #732185

# Submission time Handle Problem Language Result Execution time Memory
732185 2023-04-28T15:32:42 Z LKR__enjoyer Job Scheduling (CEOI12_jobs) C++17
100 / 100
 468 ms 14168 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[100005];
int zlicz2[100005];
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()
{ ios_base::sync_with_stdio();
    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+1);
    cout<<res<<endl;
    int curr=0;
    for(int i=1;i<=n-d;i++)
    {int licz=0;
        while(licz<res&&curr<m)
        {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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1848 KB Output is correct
2 Correct 41 ms 1756 KB Output is correct
3 Correct 42 ms 1856 KB Output is correct
4 Correct 49 ms 1756 KB Output is correct
5 Correct 53 ms 1888 KB Output is correct
6 Correct 44 ms 1764 KB Output is correct
7 Correct 43 ms 1872 KB Output is correct
8 Correct 47 ms 1864 KB Output is correct
9 Correct 155 ms 2372 KB Output is correct
10 Correct 149 ms 2368 KB Output is correct
11 Correct 39 ms 1732 KB Output is correct
12 Correct 73 ms 3068 KB Output is correct
13 Correct 123 ms 4772 KB Output is correct
14 Correct 187 ms 6000 KB Output is correct
15 Correct 190 ms 7676 KB Output is correct
16 Correct 282 ms 9272 KB Output is correct
17 Correct 316 ms 10840 KB Output is correct
18 Correct 323 ms 12316 KB Output is correct
19 Correct 468 ms 14168 KB Output is correct
20 Correct 323 ms 10712 KB Output is correct