Submission #856244

#	Time	Username	Problem	Language	Result	Execution time	Memory
856244		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	709 ms	49784 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
map<int, set<int>> pos;
int main() {
    int t = 1;
    // cin >> t;
    while(t --) {
       int n, d, m;
       cin >> n >> d >> m;
       map<int, int> mp, mp2;
       for(int i = 0, x; i < m; i ++) {
           cin >> x;
           pos[x].insert(i + 1);
           mp2[x] ++;
       }
       int l = 1, r = m;
       while(l <= r) {
           int mid = (l + r) / 2;
           mp = mp2;
           for(int i = 1; i <= n && !mp.empty(); i ++) {
               int sum = mid;
               while(!mp.empty() && mp.begin()->first <= i && sum) {
                   int x = mp.begin()->first;
                   int y = mp.begin()->second;
                   int dd = min(sum, y);
                   sum -= dd;
                   if(dd == y) mp.erase(x);
                   else mp[x] -= dd;
               }
           }
           if(mp.empty()) r = mid - 1;
           else l = mid + 1;
       }
       mp = mp2;
       cout << l << '\n';
       for(int i = 1; i <= n; i ++) {
           int sum = l;
           while(!mp.empty() && mp.begin()->first <= i && sum) {
               int x = mp.begin()->first;
               int y = mp.begin()->second;
               int dd = min(sum, y);
               sum -= dd;
               if(dd == y) mp.erase(x);
               else mp[x] -= dd;
               while(dd --) {
                   cout << *pos[x].begin() << ' ';
                   pos[x].erase(pos[x].begin());
               }
           }
           cout << "0\n";
       }
    }
    return 0;
}

• Subtask 1: 25 / 100