Submission #92078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92078	2019-01-01T11:47:39 Z	someone_aa	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	311 ms	20088 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";*/
        while(dq.front().second == 0 && dq.size()) dq.pop_front();
    }
    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;
    }
    cout<<li<<"\n";
    get_result(li);
    return 0;
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	6640 KB	Output is correct
2	Correct	33 ms	6640 KB	Output is correct
3	Correct	33 ms	6768 KB	Output is correct
4	Correct	33 ms	6640 KB	Output is correct
5	Correct	33 ms	6640 KB	Output is correct
6	Correct	34 ms	6640 KB	Output is correct
7	Correct	33 ms	6784 KB	Output is correct
8	Correct	33 ms	6940 KB	Output is correct
9	Correct	49 ms	7032 KB	Output is correct
10	Correct	49 ms	6944 KB	Output is correct
11	Correct	36 ms	6648 KB	Output is correct
12	Correct	69 ms	8380 KB	Output is correct
13	Correct	100 ms	11256 KB	Output is correct
14	Correct	170 ms	13088 KB	Output is correct
15	Correct	162 ms	13156 KB	Output is correct
16	Correct	255 ms	15400 KB	Output is correct
17	Correct	294 ms	20088 KB	Output is correct
18	Correct	257 ms	18812 KB	Output is correct
19	Correct	311 ms	19676 KB	Output is correct
20	Correct	298 ms	20064 KB	Output is correct