Submission #1122510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122510		andrewkong972	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	440 ms	13944 KiB

jobs

  #include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e5 + 5;
int n,d,m; 
vector<pair<int,int>> vec;
int jobs[SIZE];
queue<pair<int,int>> q;

bool solve(int k) {
    int av = k;
    
    for (int i=1; i<=n; i++) {
        av = k;
        if (jobs[i] > 0) q.push(make_pair(jobs[i], i+d));

        while (av > 0 && !q.empty()) {
            if (q.front().second < i) return 0;
            else {
                if (av >= q.front().first) {
                    av -= q.front().first;
                    q.pop();
                }
                else q.front().first -= av, av = 0;
            }
        }
    }

    return 1;
}

bool comp(pair<int,int> a, pair<int,int> b) {
    return (a.first != b.first ? a.first < b.first : a.second < b.second);
}

void print(int ans) {
    sort(vec.begin(), vec.end(), comp);
    int left = ans, index = 0;

    for (int i=1; i<=n; i++) {
        left = ans;        
        while (index < m && vec[index].first <= i && left > 0) {
            cout << vec[index].second << " ";
            left --, index ++ ;
        }
        cout << 0 << endl;
    }

    return;
}

int main() {
    int cur;
    cin >> n >> d >> m;
    
    for (int i=0; i<m; i++) {
        cin >> cur;
        vec.push_back(make_pair(cur, i+1));
        jobs[cur] ++;
    }

    int lp = 1, rp = m;

    while (lp < rp) {
        int mid = lp + (rp - lp)/2;
        if (solve(mid)) rp = mid;
        else lp = mid + 1;
    }

    cout << lp << endl;

    print(lp);
    return 0;
}

• Subtask 1: 50 / 100