답안 #677613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677613	2023-01-04T00:43:24 Z	tgp07	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	253 ms	31164 KB

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 = 1e8;
    hi++;
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        
        bool works = true;
        ll day = 1; ll cnt = mid;
        for (ll i = 0; i < m; 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 < m; i++) {
        if (day < requests[i].first) {
            day = requests[i].first;
            cnt = lo;
        }
        
        cnt--;
        ans[day-1].push_back(requests[i].second+1);
        //cout << requests[i].second + 1 << "LOL" << endl;
        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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	3672 KB	Output is correct
2	Correct	18 ms	3640 KB	Output is correct
3	Correct	18 ms	3584 KB	Output is correct
4	Correct	17 ms	3544 KB	Output is correct
5	Correct	18 ms	3544 KB	Output is correct
6	Correct	18 ms	3544 KB	Output is correct
7	Correct	19 ms	3596 KB	Output is correct
8	Correct	17 ms	3648 KB	Output is correct
9	Correct	32 ms	5844 KB	Output is correct
10	Correct	31 ms	5928 KB	Output is correct
11	Correct	25 ms	3412 KB	Output is correct
12	Correct	51 ms	6760 KB	Output is correct
13	Correct	77 ms	11024 KB	Output is correct
14	Correct	111 ms	14668 KB	Output is correct
15	Correct	131 ms	15552 KB	Output is correct
16	Correct	177 ms	19168 KB	Output is correct
17	Correct	197 ms	26312 KB	Output is correct
18	Correct	215 ms	26664 KB	Output is correct
19	Correct	253 ms	31164 KB	Output is correct
20	Correct	188 ms	26216 KB	Output is correct