Submission #565519

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
565519	2022-05-21T03:58:06 Z	scc_c	Job Scheduling (CEOI12_jobs)	C++14	20 / 100	374 ms	65536 KB

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<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] < curday-d) return 0;
        if(a[i] == curday-d) processing++; //if the deadline is almost up then put them as priority on the list
        else if(a[i] <= curday && processing < mach) processing++;
        if(processing == mach || i == m-1 || a[i+1] > curday){
            curday++;
            processing = 0;
        }
    }
    if(processing > mach) return 0;
    if(curday > n) return 0;
    return 1;
}

void printworks2(vector<int> a, vector<pair<int, int> > amap, 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] >= d+curday){
            cout << amap[i].second << " ";//if the deadline is almost up then put them as priority on the list
            processing++;
        }
        else if(a[i] <= curday && processing < mach){
            cout << amap[i].second << " ";
            processing++;
        }
        if(processing == mach || i == m || a[i+1] > curday){
            curday++;
            processing = 0;
            cout << 0 << endl;
        }
    }
    cout << 0 << endl;
}

void printworks(vector<int> a, vector<pair<int, int> > amap, 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] == curday-d){
            cout << amap[i].second << " ";
            processing++;
        }
        else if(a[i] <= curday && processing < mach){
            cout << amap[i].second << " ";
            processing++;
        }
        if(processing == mach || i == m || a[i+1] > curday){
            curday++;
            processing = 0;
            cout << 0 << endl;
        }
    }
    for(int i = curday; i < n+1; i++) cout << 0 << endl;
}

int binsearch(vector<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<int> a(m);
    vector<pair<int, int> > amap;

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

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	60 ms	9660 KB	Output isn't correct
2	Incorrect	51 ms	9576 KB	Output isn't correct
3	Incorrect	47 ms	9680 KB	Output isn't correct
4	Incorrect	47 ms	9704 KB	Output isn't correct
5	Incorrect	47 ms	9664 KB	Output isn't correct
6	Incorrect	55 ms	9740 KB	Output isn't correct
7	Incorrect	49 ms	9700 KB	Output isn't correct
8	Incorrect	58 ms	9632 KB	Output isn't correct
9	Correct	160 ms	9748 KB	Output is correct
10	Correct	170 ms	9656 KB	Output is correct
11	Correct	49 ms	9628 KB	Output is correct
12	Incorrect	100 ms	19084 KB	Output isn't correct
13	Correct	157 ms	28384 KB	Output is correct
14	Runtime error	229 ms	37764 KB	Memory limit exceeded
15	Runtime error	259 ms	47156 KB	Memory limit exceeded
16	Runtime error	340 ms	54176 KB	Memory limit exceeded
17	Runtime error	374 ms	65536 KB	Execution killed with signal 9
18	Runtime error	321 ms	65536 KB	Execution killed with signal 9
19	Runtime error	365 ms	65536 KB	Execution killed with signal 9
20	Runtime error	325 ms	65536 KB	Execution killed with signal 9