oj.uz

Submission #1027024

# Submission time Handle Problem Language Result Execution time Memory
1027024 2024-07-18T18:55:20 Z kkkkkkkk Job Scheduling (CEOI12_jobs) C++14
40 / 100
 222 ms 26136 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.clear();
    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:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=1;i<rez.size();i++) {
      |                  ~^~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2760 KB Output is correct
2 Correct 19 ms 2760 KB Output is correct
3 Correct 19 ms 2756 KB Output is correct
4 Correct 19 ms 2828 KB Output is correct
5 Correct 19 ms 2760 KB Output is correct
6 Correct 17 ms 2756 KB Output is correct
7 Correct 19 ms 2924 KB Output is correct
8 Correct 19 ms 2828 KB Output is correct
9 Incorrect 30 ms 7720 KB Output isn't correct
10 Incorrect 29 ms 7728 KB Output isn't correct
11 Incorrect 24 ms 2648 KB Output isn't correct
12 Incorrect 63 ms 4948 KB Output isn't correct
13 Incorrect 90 ms 8016 KB Output isn't correct
14 Incorrect 139 ms 10596 KB Output isn't correct
15 Incorrect 112 ms 12308 KB Output isn't correct
16 Incorrect 172 ms 15424 KB Output isn't correct
17 Incorrect 209 ms 18504 KB Output isn't correct
18 Incorrect 188 ms 20172 KB Output isn't correct
19 Incorrect 221 ms 26136 KB Output isn't correct
20 Incorrect 222 ms 18536 KB Output isn't correct