Submission #856242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
856242	2023-10-02T21:25:36 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	1000 ms	65536 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	58 ms	10576 KB	Output isn't correct
2	Incorrect	58 ms	10692 KB	Output isn't correct
3	Incorrect	57 ms	10824 KB	Output isn't correct
4	Incorrect	57 ms	10576 KB	Output isn't correct
5	Incorrect	68 ms	10576 KB	Output isn't correct
6	Incorrect	57 ms	10508 KB	Output isn't correct
7	Incorrect	61 ms	10580 KB	Output isn't correct
8	Incorrect	59 ms	10480 KB	Output isn't correct
9	Incorrect	65 ms	10792 KB	Output isn't correct
10	Incorrect	66 ms	10832 KB	Output isn't correct
11	Correct	108 ms	10932 KB	Output is correct
12	Correct	218 ms	21152 KB	Output is correct
13	Correct	336 ms	31392 KB	Output is correct
14	Runtime error	697 ms	42812 KB	Memory limit exceeded
15	Runtime error	630 ms	51812 KB	Memory limit exceeded
16	Execution timed out	1064 ms	60160 KB	Time limit exceeded
17	Execution timed out	1040 ms	61520 KB	Time limit exceeded
18	Runtime error	747 ms	65536 KB	Execution killed with signal 9
19	Runtime error	717 ms	65536 KB	Execution killed with signal 9
20	Execution timed out	1046 ms	58452 KB	Time limit exceeded