Submission #701404

#	Time	Username	Problem	Language	Result	Execution time	Memory
701404		aedmhsn	Job Scheduling (CEOI12_jobs)	C++17	94 / 100	359 ms	14480 KiB

jobs

#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++;
            }
            else{
                cout << v[ind].B << " ";
                cnt++;
                ind++;
            }
        }
    }
}  

• Subtask 1: 94 / 100