oj.uz

Submission #1027022

# Submission time Handle Problem Language Result Execution time Memory
1027022 2024-07-18T18:52:07 Z kkkkkkkk Job Scheduling (CEOI12_jobs) C++14
40 / 100
 192 ms 29724 KB 
#include <bits/stdc++.h>

using namespace std;

int n, d, m;
vector<pair<int,int> > v;
vector<vector<int> > rez;

bool ok(int masini) {
    int den=1;
    vector<vector<int> > raspored(n+1);
    for (int i=0;i<m;i+=masini) {
        for (int j=i;j<i+masini;j++) {
            while (v[j].first>den)
                den++;
            if (v[j].first+d<den)
                return false;
            raspored[den].push_back(v[j].second);
        }
        den++;
    }
    rez=raspored;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> d >> m;
    v.resize(m);
    for (int i=0;i<m;i++) {
        cin >> v[i].first;
        v[i].second=i+1;
    }
    sort(v.begin(), v.end());
    int l=0, r=m;
    while (l+1<r) {
        int mid=(l+r)/2;
        if (ok(mid)) r=mid;
        else l=mid;
    }
    cout << r << '\n';
    for (int i=1;i<rez.size();i++) {
        for (auto x:rez[i])
            cout << x << " ";
        cout << "0" << '\n';
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=1;i<rez.size();i++) {
      |                  ~^~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3016 KB Output is correct
2 Correct 18 ms 3016 KB Output is correct
3 Correct 16 ms 3184 KB Output is correct
4 Correct 17 ms 3016 KB Output is correct
5 Correct 18 ms 3096 KB Output is correct
6 Correct 18 ms 3012 KB Output is correct
7 Correct 22 ms 3184 KB Output is correct
8 Correct 18 ms 3012 KB Output is correct
9 Incorrect 26 ms 7988 KB Output isn't correct
10 Incorrect 28 ms 8104 KB Output isn't correct
11 Incorrect 23 ms 3164 KB Output isn't correct
12 Incorrect 45 ms 5968 KB Output isn't correct
13 Incorrect 65 ms 9056 KB Output isn't correct
14 Incorrect 115 ms 12680 KB Output isn't correct
15 Incorrect 107 ms 14160 KB Output isn't correct
16 Incorrect 155 ms 18272 KB Output isn't correct
17 Incorrect 185 ms 21608 KB Output isn't correct
18 Incorrect 158 ms 24164 KB Output isn't correct
19 Incorrect 192 ms 29724 KB Output isn't correct
20 Incorrect 192 ms 21804 KB Output isn't correct