Submission #565520

#	Time	Username	Problem	Language	Result	Execution time	Memory
565520		scc_c	Job Scheduling (CEOI12_jobs)	C++14	15 / 100	387 ms	65536 KiB

jobs

#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <sstream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <iterator>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <queue>
#include <numeric>
#include <deque>

#define lli long long int 

using namespace std;

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

int works(vector<pair<int, int> > a, int mach, int n, int m, int d){ //k groups, mid is the sum
    int curday = 1, processing = 0;
    for(int i = 0; i < m; i++){
        if(a[i].first < curday-d) return 0;
        if(a[i].first == curday-d) processing++; //if the deadline is almost up then put them as priority on the list
        else if(a[i].first <= curday && processing < mach) processing++;
        if(processing == mach || i == m-1 || a[i+1].first > curday){
            curday++;
            processing = 0;
        }
    }
    if(processing > mach) return 0;
    if(curday > n) return 0;
    return 1;
}

void printworks(vector<pair<int, int> > a, int mach, int n, int m, int d){ //k groups, mid is the sum
    int curday = 1, processing = 0;
    for(int i = 0; i < m; i++){
        if(a[i].first == curday-d){
            cout << a[i].second << " ";
            processing++;
        }
        else if(a[i].first <= curday && processing < mach){
            cout << a[i].second << " ";
            processing++;
        }
        if(processing == mach || i == m || a[i+1].first > curday){
            curday++;
            processing = 0;
            cout << 0 << endl;
        }
    }
    for(int i = curday; i < n+1; i++) cout << 0 << endl;
}

int binsearch(vector<pair<int, int> > a, int l, int r, int n, int m, int d){ //l and r are values of r
    if(l == r) return l;
    if(r == l+1){
        if(works(a, l, n, m, d)) return l;
        return r;
    }
    int mid = (r+l)/2;
    if(works(a, mid, n, m, d)) return binsearch(a, l, mid, n, m, d);
    else return binsearch(a, mid+1, r, n, m, d);
}

int main(){

    int n, d, m;
    cin >> n >> d >> m;

    vector<pair<int, int> > amap;

    for(int i = 0; i < m; i++){
        int x;
        cin >> x;
        amap.push_back(make_pair(x, i+1));
    }
    sort(amap.begin(), amap.end());
    
    int ans = binsearch(amap, 0, 1000001, n, m, d);
    cout << ans << endl;
    printworks(amap, ans, n, m, d);
    
    return 0;
}

• Subtask 1: 15 / 100