Submission #92079

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92079	2019-01-01T11:48:33 Z	someone_aa	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	189 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;
        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();
        }
        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;
        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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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;
    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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	6704 KB	Output is correct
2	Correct	22 ms	6708 KB	Output is correct
3	Correct	22 ms	6644 KB	Output is correct
4	Correct	21 ms	6640 KB	Output is correct
5	Correct	20 ms	6640 KB	Output is correct
6	Correct	21 ms	6680 KB	Output is correct
7	Correct	20 ms	6752 KB	Output is correct
8	Correct	20 ms	6772 KB	Output is correct
9	Correct	36 ms	6904 KB	Output is correct
10	Correct	38 ms	6904 KB	Output is correct
11	Correct	24 ms	6776 KB	Output is correct
12	Correct	40 ms	8388 KB	Output is correct
13	Correct	59 ms	11132 KB	Output is correct
14	Correct	102 ms	13048 KB	Output is correct
15	Correct	85 ms	13076 KB	Output is correct
16	Correct	143 ms	15388 KB	Output is correct
17	Correct	164 ms	19960 KB	Output is correct
18	Correct	144 ms	18936 KB	Output is correct
19	Correct	189 ms	19788 KB	Output is correct
20	Correct	172 ms	19960 KB	Output is correct