oj.uz

Submission #404228

# Submission time Handle Problem Language Result Execution time Memory
404228 2021-05-14T01:20:09 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
24 / 100
 644 ms 50144 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 = 1000010;

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: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+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 63 ms 26852 KB Partially correct
2 Partially correct 64 ms 26844 KB Partially correct
3 Partially correct 64 ms 26788 KB Partially correct
4 Partially correct 65 ms 26848 KB Partially correct
5 Partially correct 64 ms 26864 KB Partially correct
6 Partially correct 64 ms 26760 KB Partially correct
7 Partially correct 63 ms 26772 KB Partially correct
8 Partially correct 66 ms 26840 KB Partially correct
9 Partially correct 77 ms 26928 KB Partially correct
10 Partially correct 81 ms 26980 KB Partially correct
11 Partially correct 75 ms 26544 KB Partially correct
12 Partially correct 142 ms 29604 KB Partially correct
13 Runtime error 240 ms 33120 KB Memory limit exceeded
14 Runtime error 295 ms 37356 KB Memory limit exceeded
15 Runtime error 349 ms 38876 KB Memory limit exceeded
16 Runtime error 440 ms 43868 KB Memory limit exceeded
17 Runtime error 549 ms 48456 KB Memory limit exceeded
18 Runtime error 587 ms 47564 KB Memory limit exceeded
19 Runtime error 644 ms 50144 KB Memory limit exceeded
20 Runtime error 527 ms 48472 KB Memory limit exceeded