oj.uz

Submission #83819

# Submission time Handle Problem Language Result Execution time Memory
83819 2018-11-11T04:12:06 Z mra2322001 Job Scheduling (CEOI12_jobs) C++14
25 / 100
 342 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 58 ms 9592 KB Output isn't correct
2 Incorrect 60 ms 9732 KB Output isn't correct
3 Incorrect 58 ms 9732 KB Output isn't correct
4 Incorrect 65 ms 9764 KB Output isn't correct
5 Incorrect 60 ms 9856 KB Output isn't correct
6 Incorrect 63 ms 9856 KB Output isn't correct
7 Incorrect 59 ms 9856 KB Output isn't correct
8 Incorrect 61 ms 9888 KB Output isn't correct
9 Incorrect 247 ms 19232 KB Output isn't correct
10 Incorrect 239 ms 19244 KB Output isn't correct
11 Correct 47 ms 19244 KB Output is correct
12 Correct 77 ms 19244 KB Output is correct
13 Correct 119 ms 19244 KB Output is correct
14 Correct 210 ms 19244 KB Output is correct
15 Incorrect 206 ms 21948 KB Output isn't correct
16 Correct 294 ms 28800 KB Output is correct
17 Runtime error 342 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 276 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 312 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 342 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.