Submission #677612

#	Time	Username	Problem	Language	Result	Execution time	Memory
677612		tgp07	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	161 ms	19260 KiB

jobs

//#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
#include <bitset>
#include <iomanip>

using namespace std;

//change the long long to int if you need to save memory/time really badly
typedef long long ll;

//Comment this define when working on interactive problems
#define endl "\n"
#define sqrt(n) sqrt((long double) n)

const ll MAXN = 5e5 + 5;
const ll ZER = 0;
const ll ONE = 1;
const ll INF = LLONG_MAX;
const ll MOD = 998244353;

void solve(ll ca) {
    ll n, d, m;
    cin >> n >> d >> m;
    
    pair<ll, ll> requests[m];
    for (ll i = 0; i < m; i++) {
        cin >> requests[i].first;
        requests[i].second = i;
    }
    sort(requests, requests+m);
    
    ll lo = 1; ll hi = 1e6;
    hi++;
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        
        bool works = true;
        ll day = 1; ll cnt = mid;
        for (ll i = 0; i < n; i++) {
            if (day < requests[i].first) {
                day = requests[i].first;
                cnt = mid;
            }
            
            if (abs(day - requests[i].first) > d) {
                works = false;
                break;
            }
            
            cnt--;
            if (cnt == 0) {
                day++;
                cnt = mid;
            }
        }
        
        if (works) {
            hi = mid;
        } else {
            lo = mid+1;
        }
    }
    
    cout << lo << endl;
    vector<ll> ans[n];
    
    ll day = 1; ll cnt = lo;
    for (ll i = 0; i < n; i++) {
        if (day < requests[i].first) {
            day = requests[i].first;
            cnt = lo;
        }
        
        cnt--;
        ans[day-1].push_back(requests[i].second+1);
        if (cnt == 0) {
            day++;
            cnt = lo;
        }
    }
    
    for (ll i = 0; i < n; i++) {
        for (auto el: ans[i]) {
            cout << el << " ";
        }
        cout << 0 << endl;
    }
    
    return;
}

int main()
{
    //Fast IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll t = 1;
    //cin >> t;
        
    ll co = 1;
    while (t--) {
        solve(co);
        ++co;
    }
}

• Subtask 1: 10 / 100