답안 #92079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92079 2019-01-01T11:48:33 Z someone_aa Job Scheduling (CEOI12_jobs) C++17
100 / 100
189 ms 19960 KB
#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;
}
# 결과 실행 시간 메모리 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