oj.uz

Submission #732183

# Submission time Handle Problem Language Result Execution time Memory
732183 2023-04-28T15:31:06 Z LKR__enjoyer Job Scheduling (CEOI12_jobs) C++17
80 / 100
 372 ms 22208 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;
        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 50 ms 1848 KB Output is correct
2 Correct 42 ms 1856 KB Output is correct
3 Correct 40 ms 1752 KB Output is correct
4 Correct 43 ms 1860 KB Output is correct
5 Correct 40 ms 1816 KB Output is correct
6 Correct 47 ms 1860 KB Output is correct
7 Correct 41 ms 1872 KB Output is correct
8 Correct 42 ms 1852 KB Output is correct
9 Runtime error 40 ms 3680 KB Execution killed with signal 11
10 Runtime error 43 ms 3648 KB Execution killed with signal 11
11 Correct 40 ms 1724 KB Output is correct
12 Correct 80 ms 3148 KB Output is correct
13 Correct 120 ms 4684 KB Output is correct
14 Correct 182 ms 6100 KB Output is correct
15 Correct 204 ms 7752 KB Output is correct
16 Correct 275 ms 9320 KB Output is correct
17 Correct 323 ms 10900 KB Output is correct
18 Runtime error 372 ms 19460 KB Execution killed with signal 11
19 Runtime error 364 ms 22208 KB Execution killed with signal 11
20 Correct 338 ms 10888 KB Output is correct