Submission #416750

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416750	2021-06-02T21:41:24 Z	winstonyin	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	639 ms	21036 KB

jobs

#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <map>
#include <set>
#include <fstream>
#include <unordered_map>
#include <queue>
using namespace std;
using pi = pair<int, int>;
using pd = pair<double, double>; 
#define ll long long
#define all(x) (x).begin(), (x).end()
ll  days, delay, requests;
vector<pair<ll,ll>> seq;
bool works(ll  machines) {
    if(days*machines < requests) {
        return false;
    }
    ll  cur_day = 0; ll  cur_req = 0;
    while(cur_day < days && cur_req < requests) {
        for(ll  j = 0; j < machines; j++) {
            if(cur_req == requests) {
                break;
            }
            if(seq[cur_req].first <= cur_day+1) {
                if(cur_day+1 - seq[cur_req].first <= delay) {
                    cur_req++;
                }
                else {
                    return false;
                }
            }
            else {
                j = machines;
            }
        }
        cur_day++;
    }
    return cur_req == requests && cur_day <= days;
}
bool p_works(ll  machines) {
    if(days*machines < requests) {
        return false;
    }
    ll  cur_day = 0; ll  cur_req = 0;
    while(cur_day < days && cur_req < requests) {
        for(ll  j = 0; j < machines; j++) {
            if(cur_req == requests) {
                break;
            }
            if(seq[cur_req].first <= cur_day+1) {
                if(cur_day+1 - seq[cur_req].first <= delay) {
                    cout << seq[cur_req].second << " ";
                    cur_req++;
                }
                else {
                    return false;
                }
            }
            else {
                j = machines;
            }
        }
        cout << 0 << endl;
        cur_day++;
    }
    while(cur_day < days) {
        cout << 0 << endl;
        cur_day++;
    }
    return cur_req == requests && cur_day <= days;
}
int  main() {
    cin >> days >> delay >> requests;
    for(ll  i = 0; i < requests; i++) {
        ll  day; cin >> day;
        seq.push_back({day, i+1});
    }
    sort(all(seq));
    ll  a = 1, b = 1e9;
    ll  ans;
    while(a <= b) {
        ll  mid = (a+b)/2;
        // cout << a << " " << b << endl;
        if(works(mid)) {
            ans = mid;
            b = mid-1;
        }
        else {
            a = mid+1;
        }
    }
    cout << ans << endl;
    p_works(ans);
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:100:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     p_works(ans);
      |     ~~~~~~~^~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	2728 KB	Output is correct
2	Correct	58 ms	2616 KB	Output is correct
3	Correct	56 ms	2504 KB	Output is correct
4	Correct	56 ms	2508 KB	Output is correct
5	Correct	55 ms	2532 KB	Output is correct
6	Correct	57 ms	2504 KB	Output is correct
7	Correct	58 ms	2548 KB	Output is correct
8	Correct	57 ms	2640 KB	Output is correct
9	Correct	200 ms	2716 KB	Output is correct
10	Correct	201 ms	2704 KB	Output is correct
11	Correct	52 ms	2460 KB	Output is correct
12	Correct	104 ms	4752 KB	Output is correct
13	Correct	157 ms	8608 KB	Output is correct
14	Correct	236 ms	9292 KB	Output is correct
15	Correct	259 ms	11596 KB	Output is correct
16	Correct	356 ms	16776 KB	Output is correct
17	Correct	407 ms	16792 KB	Output is correct
18	Correct	456 ms	18440 KB	Output is correct
19	Correct	639 ms	21036 KB	Output is correct
20	Correct	415 ms	16872 KB	Output is correct