oj.uz

Submission #83820

# Submission time Handle Problem Language Result Execution time Memory
83820 2018-11-11T04:12:39 Z mra2322001 Job Scheduling (CEOI12_jobs) C++14
25 / 100
 338 ms 33792 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, d, m;
pair <int, pair <int, int> > a[N*10];
vector <vector <int> > v, b;

bool check(int x){
    f1(i, n) v[i].clear();
    int ma = a[1].first, cur = 0;
    f1(i, m){
        while(ma < a[i].first) ma++;
        cur++;
        if(cur <= x){
            v[ma].emplace_back(a[i].second.second);
        }
        else{
            cur = 1;
            ma++;
            if(ma > n) return 0;
            v[ma].emplace_back(a[i].second.second);
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> d >> m;
    v.resize(n + 1);
    b.resize(n + 1);
    f1(i, m){
        int x; cin >> x;
        a[i] = {x, {x + d, i}};
    }
    sort(a + 1, a + m + 1);

    int l = 1, r = n, ans = n;
    while(l <= r){
        int mid = (l + r)/2;
        if(check(mid)){
            r = mid - 1, ans = mid;
            f1(i, n){
                b[i].clear();
                for(auto x:v[i]){
                    b[i].emplace_back(x);
                }
            }
        }
        else l = mid + 1;
    }
    cout << ans << endl;
    f1(i, n){
        for(auto x:b[i]) cout << x << " ";
        cout << 0 << endl;
    }
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 9592 KB Output isn't correct
2 Incorrect 61 ms 9752 KB Output isn't correct
3 Incorrect 61 ms 9752 KB Output isn't correct
4 Incorrect 61 ms 9752 KB Output isn't correct
5 Incorrect 59 ms 9752 KB Output isn't correct
6 Incorrect 66 ms 9792 KB Output isn't correct
7 Incorrect 59 ms 9824 KB Output isn't correct
8 Incorrect 62 ms 9944 KB Output isn't correct
9 Incorrect 262 ms 19224 KB Output isn't correct
10 Incorrect 273 ms 19316 KB Output isn't correct
11 Correct 43 ms 19316 KB Output is correct
12 Correct 107 ms 19316 KB Output is correct
13 Correct 121 ms 19316 KB Output is correct
14 Correct 214 ms 19316 KB Output is correct
15 Incorrect 196 ms 21920 KB Output isn't correct
16 Correct 302 ms 28892 KB Output is correct
17 Runtime error 338 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
18 Runtime error 282 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 315 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 332 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.