oj.uz

Submission #1027041

# Submission time Handle Problem Language Result Execution time Memory
1027041 2024-07-18T19:14:36 Z kkkkkkkk Job Scheduling (CEOI12_jobs) C++14
100 / 100
 203 ms 26924 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 17 ms 2756 KB Output is correct
2 Correct 22 ms 2760 KB Output is correct
3 Correct 19 ms 2756 KB Output is correct
4 Correct 19 ms 2756 KB Output is correct
5 Correct 19 ms 2760 KB Output is correct
6 Correct 19 ms 2804 KB Output is correct
7 Correct 19 ms 2760 KB Output is correct
8 Correct 19 ms 2756 KB Output is correct
9 Correct 35 ms 7732 KB Output is correct
10 Correct 32 ms 7732 KB Output is correct
11 Correct 22 ms 2780 KB Output is correct
12 Correct 45 ms 5204 KB Output is correct
13 Correct 66 ms 8272 KB Output is correct
14 Correct 100 ms 11552 KB Output is correct
15 Correct 99 ms 12552 KB Output is correct
16 Correct 143 ms 15460 KB Output is correct
17 Correct 180 ms 19856 KB Output is correct
18 Correct 175 ms 20584 KB Output is correct
19 Correct 203 ms 26924 KB Output is correct
20 Correct 171 ms 19780 KB Output is correct