oj.uz

Submission #489126

# Submission time Handle Problem Language Result Execution time Memory
489126 2021-11-21T08:49:00 Z ak2006 Job Scheduling (CEOI12_jobs) C++14
70 / 100
 854 ms 65544 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int t,d,m;
    cin>>t>>d>>m;
    vvi jobs(m,vi(2));
    for (int i = 0;i<m;i++)cin>>jobs[i][0],jobs[i][1] = i + 1;
    sort(jobs.begin(),jobs.end());
    int l = 1,r = m,ans = 1;
    vvi out;
    while (l <= r){
        int mid = (l + r)/2;
        bool is = true;
        int pos = 0,day = 1;
        vvi cur(t);
        while (day <= t and pos <= m){
            for (int mach = 0;mach < mid;mach++){
                if (pos == m)break;
                if (jobs[pos][0] + d < day){
                    is = false;
                    break;
                }
                if (jobs[pos][0] > day)break;
                cur[day - 1].pb(jobs[pos][1]);
                pos++;
            }   
            if (!is)break;
            day++;
        }
        if (is and pos == m){
            ans = mid;
            r = mid - 1;
            out = cur;
        }
        else l = mid + 1;
    }
    cout<<ans<<"\n";
    for (auto it:out){
        for (auto it2:it)cout<<it2<<" ";
        cout<<0<<"\n";
    }
    return 0;
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7312 KB Output is correct
2 Correct 34 ms 7308 KB Output is correct
3 Correct 34 ms 7384 KB Output is correct
4 Correct 37 ms 7360 KB Output is correct
5 Correct 34 ms 7328 KB Output is correct
6 Correct 33 ms 7304 KB Output is correct
7 Correct 34 ms 7316 KB Output is correct
8 Correct 33 ms 7328 KB Output is correct
9 Correct 73 ms 12268 KB Output is correct
10 Correct 66 ms 12412 KB Output is correct
11 Correct 48 ms 7448 KB Output is correct
12 Correct 143 ms 14660 KB Output is correct
13 Correct 254 ms 22256 KB Output is correct
14 Correct 388 ms 30308 KB Output is correct
15 Runtime error 409 ms 36016 KB Memory limit exceeded
16 Runtime error 579 ms 43612 KB Memory limit exceeded
17 Runtime error 712 ms 52728 KB Memory limit exceeded
18 Runtime error 854 ms 58072 KB Memory limit exceeded
19 Runtime error 747 ms 65544 KB Execution killed with signal 9
20 Runtime error 681 ms 52768 KB Memory limit exceeded