oj.uz

Submission #83818

# Submission time Handle Problem Language Result Execution time Memory
83818 2018-11-11T04:11:29 Z mra2322001 Job Scheduling (CEOI12_jobs) C++14
25 / 100
 351 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 59 ms 9592 KB Output isn't correct
2 Incorrect 64 ms 9604 KB Output isn't correct
3 Incorrect 66 ms 9652 KB Output isn't correct
4 Incorrect 58 ms 9652 KB Output isn't correct
5 Incorrect 59 ms 9684 KB Output isn't correct
6 Incorrect 64 ms 9704 KB Output isn't correct
7 Incorrect 60 ms 9704 KB Output isn't correct
8 Incorrect 58 ms 9812 KB Output isn't correct
9 Incorrect 252 ms 19220 KB Output isn't correct
10 Incorrect 245 ms 19220 KB Output isn't correct
11 Correct 44 ms 19220 KB Output is correct
12 Correct 79 ms 19220 KB Output is correct
13 Correct 133 ms 19220 KB Output is correct
14 Correct 195 ms 19220 KB Output is correct
15 Incorrect 199 ms 21916 KB Output isn't correct
16 Correct 289 ms 28828 KB Output is correct
17 Runtime error 328 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 298 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 313 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 351 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.