Submission #92075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92075	2019-01-01T11:30:03 Z	someone_aa	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	366 ms	20060 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 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:94: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	33 ms	6768 KB	Output is correct
2	Correct	34 ms	6640 KB	Output is correct
3	Correct	34 ms	6640 KB	Output is correct
4	Correct	34 ms	6640 KB	Output is correct
5	Correct	32 ms	6640 KB	Output is correct
6	Correct	32 ms	6768 KB	Output is correct
7	Correct	34 ms	6768 KB	Output is correct
8	Correct	32 ms	6640 KB	Output is correct
9	Correct	46 ms	6984 KB	Output is correct
10	Correct	48 ms	6908 KB	Output is correct
11	Correct	36 ms	6648 KB	Output is correct
12	Incorrect	67 ms	8312 KB	Output isn't correct
13	Correct	99 ms	11228 KB	Output is correct
14	Incorrect	166 ms	13048 KB	Output isn't correct
15	Correct	162 ms	13104 KB	Output is correct
16	Correct	251 ms	15428 KB	Output is correct
17	Correct	298 ms	19916 KB	Output is correct
18	Correct	251 ms	18936 KB	Output is correct
19	Correct	305 ms	19708 KB	Output is correct
20	Correct	366 ms	20060 KB	Output is correct