oj.uz

Submission #404225

# Submission time Handle Problem Language Result Execution time Memory
404225 2021-05-14T01:14:48 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
55 / 100
 630 ms 32352 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 = 1e5;

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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 52 ms 6012 KB Partially correct
2 Partially correct 54 ms 5940 KB Partially correct
3 Partially correct 53 ms 6000 KB Partially correct
4 Partially correct 52 ms 5960 KB Partially correct
5 Partially correct 55 ms 6012 KB Partially correct
6 Partially correct 53 ms 6000 KB Partially correct
7 Partially correct 53 ms 5940 KB Partially correct
8 Partially correct 54 ms 5948 KB Partially correct
9 Partially correct 65 ms 6088 KB Partially correct
10 Partially correct 65 ms 6188 KB Partially correct
11 Partially correct 68 ms 5796 KB Partially correct
12 Partially correct 131 ms 9268 KB Partially correct
13 Correct 194 ms 13052 KB Output is correct
14 Partially correct 316 ms 18124 KB Partially correct
15 Partially correct 335 ms 19792 KB Partially correct
16 Correct 438 ms 25600 KB Output is correct
17 Correct 507 ms 30588 KB Output is correct
18 Correct 563 ms 29364 KB Output is correct
19 Partially correct 630 ms 32352 KB Partially correct
20 Correct 519 ms 30640 KB Output is correct