oj.uz

Submission #701406

# Submission time Handle Problem Language Result Execution time Memory
701406 2023-02-21T07:52:01 Z aedmhsn Job Scheduling (CEOI12_jobs) C++17
100 / 100
 365 ms 13844 KB 
#include <bits/stdc++.h>
using namespace std;
 
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
 
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

const int mxN=1e5+5;


int main(){
    int n, d, m;
    cin >> n >> d >> m;
    vector <pii> v;
    for(int i=1; i<=m; i++){
        int x;
        cin >> x;
        v.push_back({x, i});
    }
    sort(v.begin(), v.end());
    ll st=1, en=1e6, mid, ans=1;
    while(st<=en){
        mid=(st+en)/2;
        int curday=-1, cntday=0;
        bool valid=true;
        for(int i=0; i<m; i++){
            if(v[i].A > curday){
                curday=v[i].A;
                cntday=0;
            }
            if(curday > v[i].A+d){
                valid=false;
                break;
            }
            else{
                cntday++;
                if(cntday == mid){
                    curday++;
                    cntday=0;
                }
            }
        }
        if(valid){
            ans = mid;
            en = mid-1;
        }
        else
            st = mid+1;
    }
    cout << ans << '\n';
    int ind=0, cnt=0;
    for(int i=1; i<=n;){
        if(ind == m|| cnt == ans){
            cout << 0 << '\n';
            i++;
            cnt=0;
        }
        else{
            if(v[ind].A > i){
                cout << 0 << '\n';
                i++;
                cnt=0;
            }
            else{
                cout << v[ind].B << " ";
                cnt++;
                ind++;
            }
        }
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1708 KB Output is correct
2 Correct 35 ms 1712 KB Output is correct
3 Correct 32 ms 1696 KB Output is correct
4 Correct 43 ms 1712 KB Output is correct
5 Correct 32 ms 1816 KB Output is correct
6 Correct 30 ms 1756 KB Output is correct
7 Correct 32 ms 1736 KB Output is correct
8 Correct 31 ms 1752 KB Output is correct
9 Correct 42 ms 1984 KB Output is correct
10 Correct 50 ms 1964 KB Output is correct
11 Correct 40 ms 1792 KB Output is correct
12 Correct 81 ms 3184 KB Output is correct
13 Correct 128 ms 4744 KB Output is correct
14 Correct 217 ms 6228 KB Output is correct
15 Correct 200 ms 7768 KB Output is correct
16 Correct 256 ms 9172 KB Output is correct
17 Correct 310 ms 10628 KB Output is correct
18 Correct 323 ms 12144 KB Output is correct
19 Correct 365 ms 13844 KB Output is correct
20 Correct 318 ms 10732 KB Output is correct