oj.uz

Submission #853170

# Submission time Handle Problem Language Result Execution time Memory
853170 2023-09-23T15:15:50 Z mall0809 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 310 ms 13868 KB 
#include <bits/stdc++.h>

#define __gcd() gcd()
#define C int(1e5+7)
#define M int(1e9+7)
#define el '\n'
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
typedef long long ll;

int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen("","r",stdin);
    //freopen("","w",stdout);

    int n,d,m;cin>>n>>d>>m;
    vector<array<int,2>> a(m);for(int i=0;i<m;i++)cin>>a[i][0],a[i][1] = i;
    sort(all(a));
    int l=1,r=1e7;
    auto check = [&](int mid){
        int id = 0,cnt=mid;
        for(int i=1;i<=n && id < m;i++){
            if(i > a[id][0] + d)return false;
            while(id < m && a[id][0] <= i && cnt>=1)cnt--,id++;
            cnt = mid;
        }
        return true;
    };
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<r<<el;
    int cnt = r;
    for(int i=1,id=0;i<=n;i++){
        while(id < m && a[id][0] <= i && cnt >= 1){
            cout<<a[id][1]+1<<' ';
            cnt--,id++;
        }
        cnt = r;
        cout<<0<<el;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1624 KB Output is correct
2 Correct 25 ms 1624 KB Output is correct
3 Correct 25 ms 1808 KB Output is correct
4 Correct 25 ms 1624 KB Output is correct
5 Correct 26 ms 1872 KB Output is correct
6 Correct 26 ms 1720 KB Output is correct
7 Correct 26 ms 1616 KB Output is correct
8 Correct 28 ms 1716 KB Output is correct
9 Correct 36 ms 1872 KB Output is correct
10 Correct 37 ms 1872 KB Output is correct
11 Correct 33 ms 1616 KB Output is correct
12 Correct 65 ms 3152 KB Output is correct
13 Correct 120 ms 4688 KB Output is correct
14 Correct 151 ms 6280 KB Output is correct
15 Correct 166 ms 7504 KB Output is correct
16 Correct 222 ms 9296 KB Output is correct
17 Correct 256 ms 10576 KB Output is correct
18 Correct 286 ms 12072 KB Output is correct
19 Correct 310 ms 13868 KB Output is correct
20 Correct 260 ms 10568 KB Output is correct