oj.uz

Submission #404226

# Submission time Handle Problem Language Result Execution time Memory
404226 2021-05-14T01:15:35 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
24 / 100
 641 ms 50256 KB 
// Author : Jad Isaac
// ID: jadDebugs
// TASK: -----
// LANG: C++                 

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<int, int>

const int hi = 1e6;

int n, d, m;
vector<int> ans[hi];

bool works(int robots, vector<pii> jobs)
{
    for (int i = 0; i < n; i++)
        ans[i].clear();

    int endT[robots] = {0};
    int maxD = 0;
    for (int i = 0, cur = 0; i < m; i++, cur++) {
        if (cur == robots)
            cur = 0;
        // if our end time for this job is > than our start time for this job
        // there will be delay
        if (endT[cur] + 1 > jobs[i].f) {
            endT[cur]++;
            maxD = max(maxD, endT[cur] - jobs[i].f);
        }
        else
            endT[cur] = jobs[i].f;
        ans[endT[cur]].push_back(jobs[i].s);
    }
    return maxD <= d;
}

void setIO(string name = "") {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    if ((int)(name).size()) {
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }   
}


int main()
{
    //setIO("");

    cin >> n >> d >> m;

    // first = day of req
    // second = id or req
    vector<pii> jobs(m);

    for (int i = 0; i < m; i++) {
        cin >> jobs[i].f;
        jobs[i].s = i+1;
    }
    sort(begin(jobs), end(jobs));
    int l = 0, r = m;

    while (l < r) {
        int mid = l + (r-l)/2;
        if (works(mid, jobs))
            r = mid;
        else
            l = mid+1;
    }
    cout << l << '\n';
    for (int i = 0; i < n; i++) {
        for (int x: ans[i])
            cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 63 ms 26804 KB Partially correct
2 Partially correct 63 ms 26840 KB Partially correct
3 Partially correct 63 ms 26852 KB Partially correct
4 Partially correct 67 ms 26804 KB Partially correct
5 Partially correct 65 ms 26852 KB Partially correct
6 Partially correct 63 ms 26852 KB Partially correct
7 Partially correct 66 ms 26804 KB Partially correct
8 Partially correct 63 ms 26836 KB Partially correct
9 Partially correct 76 ms 26972 KB Partially correct
10 Partially correct 78 ms 27056 KB Partially correct
11 Partially correct 77 ms 26548 KB Partially correct
12 Partially correct 144 ms 29608 KB Partially correct
13 Runtime error 215 ms 33076 KB Memory limit exceeded
14 Runtime error 294 ms 37328 KB Memory limit exceeded
15 Runtime error 346 ms 38856 KB Memory limit exceeded
16 Runtime error 446 ms 43860 KB Memory limit exceeded
17 Runtime error 522 ms 48596 KB Memory limit exceeded
18 Runtime error 558 ms 47564 KB Memory limit exceeded
19 Runtime error 641 ms 50256 KB Memory limit exceeded
20 Runtime error 530 ms 48444 KB Memory limit exceeded