oj.uz

Submission #783527

# Submission time Handle Problem Language Result Execution time Memory
783527 2023-07-15T02:52:19 Z jnjwnwnw Job Scheduling (CEOI12_jobs) C++11
100 / 100
 409 ms 14192 KB 
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
#define MAXM 1000001
#define d first
#define id second
typedef pair<int, int> request; // day, id

int n, D, m;
request requests[MAXM];

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

bool works(int numMachines);

int main(){
    cin >> n >> D >> m;
    for(int i = 0; i < m; i++){
        cin >> requests[i].d;
        requests[i].id = i;
    }
    sort(requests, requests+m);
    int lb = 1, ub = m;
    int mid;
    while (lb != ub){
        mid = (lb+ub)/2;
        if (works(mid)){
            // works with this many machines, so try less
            ub = mid;
        }else{
            // doesnt work, so try more
            lb = mid+1;
        }
    }

    cout << lb << endl;
    int idx = 0;
    for(int i = 0; i < n; i++){
        int end = min(m, idx+lb);
        for(;idx<end;idx++){
            if (requests[idx].d > i+1) break;
            cout << requests[idx].id+1 << " ";
        }
        cout << 0 << endl;
    }
}

bool works(int numMachines){
    // cout << endl << endl << numMachines << endl;
    int curNum = numMachines, day = 1;
    for(int i = 0; i < m; i++){
        if (requests[i].d > day) {day = requests[i].d; curNum = numMachines;}
        if (requests[i].d+D < day) return false; // you had to finish it before today, as now it has been S-D days
        curNum--;
        if (curNum == 0) {curNum = numMachines; day++;}
    } return true;
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1996 KB Output is correct
2 Correct 33 ms 1868 KB Output is correct
3 Correct 41 ms 1964 KB Output is correct
4 Correct 38 ms 1976 KB Output is correct
5 Correct 33 ms 1888 KB Output is correct
6 Correct 33 ms 1984 KB Output is correct
7 Correct 32 ms 1872 KB Output is correct
8 Correct 33 ms 1928 KB Output is correct
9 Correct 128 ms 2088 KB Output is correct
10 Correct 127 ms 2084 KB Output is correct
11 Correct 33 ms 1996 KB Output is correct
12 Correct 70 ms 3640 KB Output is correct
13 Correct 98 ms 5084 KB Output is correct
14 Correct 173 ms 6612 KB Output is correct
15 Correct 164 ms 8040 KB Output is correct
16 Correct 221 ms 9564 KB Output is correct
17 Correct 269 ms 11060 KB Output is correct
18 Correct 266 ms 12588 KB Output is correct
19 Correct 409 ms 14192 KB Output is correct
20 Correct 278 ms 11008 KB Output is correct