oj.uz

Submission #1085544

# Submission time Handle Problem Language Result Execution time Memory
1085544 2024-09-08T11:52:37 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 233 ms 26928 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 baranje=0;
    vector<vector<int> > raspored(n+1);
    for (int den=1;den<=n;den++) {
        for (int i=0;i<masini;i++) {
            if (v[baranje].first>den)
                break;
            if (v[baranje].first+d<den)
                return false;
            raspored[den].push_back(v[baranje].second);
            baranje++;
            if (baranje==m) {
                rez=raspored;
                return true;
            }
        }
    }
    return false;
}
 
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:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=1;i<rez.size();i++) {
      |                  ~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2760 KB Output is correct
2 Correct 21 ms 2764 KB Output is correct
3 Correct 19 ms 2760 KB Output is correct
4 Correct 21 ms 2760 KB Output is correct
5 Correct 23 ms 2760 KB Output is correct
6 Correct 19 ms 2756 KB Output is correct
7 Correct 19 ms 2924 KB Output is correct
8 Correct 19 ms 2760 KB Output is correct
9 Correct 41 ms 7724 KB Output is correct
10 Correct 31 ms 7716 KB Output is correct
11 Correct 23 ms 2904 KB Output is correct
12 Correct 48 ms 5204 KB Output is correct
13 Correct 66 ms 8272 KB Output is correct
14 Correct 110 ms 11368 KB Output is correct
15 Correct 109 ms 12572 KB Output is correct
16 Correct 151 ms 15464 KB Output is correct
17 Correct 185 ms 19816 KB Output is correct
18 Correct 184 ms 20556 KB Output is correct
19 Correct 233 ms 26928 KB Output is correct
20 Correct 182 ms 19784 KB Output is correct