Submission #498181

#	Time	Username	Problem	Language	Result	Execution time	Memory
498181		AmirElarbi	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	505 ms	13788 KiB

jobs

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 200005;
int n,d,m;
vii s;
int main(){
    cin >> n >> d >> m;
    for (int i = 0; i < m; ++i)
    {
        int a;
        cin >> a;
        s.pb({a,i});
    }
    sort(s.begin(), s.end());
    int l = 1, r = 1e6;
    while(l < r){
        int md=(l+r)/2;
        int done = 0;
        for (int i = 1; i <= n; ++i)
        {   
            if(done == m) break; 
            if(i-s[done+1].fi > d){ 
                done = -1;
                break;
            }
            int p = upper_bound(s.begin(), s.end(),mp(i,(int)(1e7)))-s.begin();
            done += min(p-done,md);
        }
        if(done == m){
            r = md;
        } else {
            l = md + 1;
        }
    }
    int res = (l+r)/2;
    cout << res << endl;
    int done = -1;
    for (int i = 1; i <= n; ++i)
    {   
        if(done == m){
            cout << 0 << endl;
        } else {
            int p = upper_bound(s.begin(), s.end(),mp(i,(int)(1e7)))-s.begin();
            for (int i = done+1; i <= min(min(p,res+done),m-1); ++i)
            {
                cout << s[i].se+1 << " ";
            }
            cout << 0 << endl;
            done += min(p-done,res);
            //cout << done << " " << p-done << endl;
        }
    }
}

• Subtask 1: 90 / 100