Submission #856242

#	Time	Username	Problem	Language	Result	Execution time	Memory
856242		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	1064 ms	65536 KiB

jobs

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

int main() {
    // setIO("milkvisits");
    int t = 1;
    // cin >> t;
    while(t --) {
       int n, d, m;
       cin >> n >> d >> m;
       multiset<int> st, st2;
       map<int, int> mp, mp2;
       map<int, set<int>> pos;
       for(int i = 0, x; i < m; i ++) {
           cin >> x;
           pos[x].insert(i);
           mp2[x] ++;
           st.insert(x);
       }
       int l = 1, r = n;
       while(l <= r) {
           int mid = l + r >> 1;
           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(auto x : pos) {
           // cerr << x.first << " : ";
           // for(auto y : x.second) cerr << y << ' ';
           // cerr << '\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 << 1 + *pos[x].begin() << ' ';
                   pos[x].erase(*pos[x].begin());
               }
           }
           cout << "0\n";
       }
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:22:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |            int mid = l + r >> 1;
      |                      ~~^~~

• Subtask 1: 15 / 100