Submission #92076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92076	2019-01-01T11:33:00 Z	someone_aa	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	305 ms	19960 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int n, d, m, x;
int arr[maxn];
vector<int>v[maxn];
vector<int>result[maxn];
bool check(int x) {
    deque<pair<int,int> > dq;
    for(int i=1;i<=n;i++) {
        dq.pb(mp(i, arr[i]));
        int value = x;

        /*cout<<"Before processing: \n";
        for(auto i:dq) {
            cout<<i.first<<" "<<i.second<<"\n";
        }*/

        while(value > 0 && dq.size()) {
            if(dq.front().first < i - d) return false;
            if(dq.front().second <= value) {
                value -= dq.front().second;
                dq.front().second = 0;
            }
            else {
                dq.front().second -= value;
                value = 0;
            }

            if(dq.front().second == 0) dq.pop_front();

        }

        /*cout<<"After processing: \n";
        for(auto i:dq) {
            cout<<i.first<<" "<<i.second<<"\n";
        }
        cout<<"--->\n";*/

    }
    return dq.size() == 0;
}

void get_result(int x) {
    deque<pair<int,int> > dq;
    for(int i=1;i<=n;i++) {
        dq.pb(mp(i, arr[i]));
        int value = x;

        /*cout<<"Before processing: \n";
        for(auto i:dq) {
            cout<<i.first<<" "<<i.second<<"\n";
        }*/

        while(value > 0 && dq.size()) {
            if(dq.front().second <= value) {
                value -= dq.front().second;
                for(int j=0;j<dq.front().second;j++) {
                    result[i].pb(v[dq.front().first].back());
                    v[dq.front().first].pop_back();
                }
                dq.front().second = 0;
            }
            else {
                dq.front().second -= value;
                for(int j=0;j<value;j++) {
                    result[i].pb(v[dq.front().first].back());
                    v[dq.front().first].pop_back();
                }
                value = 0;
            }
            if(dq.front().second == 0) dq.pop_front();
        }
    }

    for(int i=1;i<=n;i++) {
        for(int j:result[i]) cout<<j<<" ";
        cout<<"0\n";
    }
}

int main() {
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++) {
        cin>>x;
        arr[x]++;
        v[x].pb(i);
    }

    int maxv = 0;
    for(int i=1;i<=n;i++) {
        maxv = max(maxv, arr[i]);
    }

    int li = 1, ri = m;
    int answ = INT_MAX;
    while(li < ri) {
        int mid = (li+ri)/2;
        if(check(mid)) ri = mid;
        else li = mid + 1;
    }
    if(!check(li)) li = maxv;
    cout<<li<<"\n";
    get_result(li);
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:99:9: warning: unused variable 'answ' [-Wunused-variable]
     int answ = INT_MAX;
         ^~~~

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	6644 KB	Output is correct
2	Correct	33 ms	6640 KB	Output is correct
3	Correct	34 ms	6764 KB	Output is correct
4	Correct	34 ms	6684 KB	Output is correct
5	Correct	33 ms	6640 KB	Output is correct
6	Correct	33 ms	6768 KB	Output is correct
7	Correct	35 ms	6644 KB	Output is correct
8	Correct	34 ms	6640 KB	Output is correct
9	Correct	48 ms	6904 KB	Output is correct
10	Correct	48 ms	6908 KB	Output is correct
11	Correct	36 ms	6776 KB	Output is correct
12	Incorrect	70 ms	8312 KB	Output isn't correct
13	Correct	100 ms	11256 KB	Output is correct
14	Incorrect	169 ms	13020 KB	Output isn't correct
15	Correct	164 ms	13048 KB	Output is correct
16	Correct	256 ms	15352 KB	Output is correct
17	Correct	305 ms	19924 KB	Output is correct
18	Correct	251 ms	18808 KB	Output is correct
19	Correct	304 ms	19832 KB	Output is correct
20	Correct	283 ms	19960 KB	Output is correct