Submission #730283

#	Time	Username	Problem	Language	Result	Execution time	Memory
730283		reestear	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	367 ms	16516 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
const int mxN = 100000;
int n, d, m;
vector <int> arr[mxN + 1];

bool check(int mid){
    queue <int> q;
    int res = 0;
    for(int i = 1; i <= n; i++){
        for(const auto &now : arr[i]){
            q.push(i);
        }
        if(!q.empty()) res = max(res, i - q.front());
        for(int j = 0; j < mid && !q.empty(); j++) q.pop();
    }

    return res <= d;
}

int main(){
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++){
        int temp; cin >> temp;
        arr[temp].push_back(i + 1);
    }

    // for(int i = 1; i <= n; i++){
    //     cout << "day = " << i << " : ";
    //     for(const auto &now : arr[i]){
    //         cout << now << ' ';
    //     }
    //     cout << '\n';
    // }
    

    int low = 1, high = m;
    while(low <= high){
        int mid = (low + high) / 2;
        cout << "mid = " << mid << '\n';
        if(check(mid)) high = mid - 1;
        else low = mid + 1;
    }

    int tot = high + 1;
    cout << tot << '\n';

    queue <int> q;
    for(int i = 1; i <= n; i++){
        for(const auto &now : arr[i]){
            q.push(now);
        }
        for(int j = 0; j < tot && !q.empty(); j++) {
            cout << q.front() << ' ';
            q.pop();
        }
        cout << "0\n";
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:11:25: warning: unused variable 'now' [-Wunused-variable]
   11 |         for(const auto &now : arr[i]){
      |                         ^~~

• Subtask 1: 0 / 100