Submission #416750

#	Time	Username	Problem	Language	Result	Execution time	Memory
416750		winstonyin	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	639 ms	21036 KiB

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 (stderr)

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 / 100