oj.uz

Submission #481744

# Submission time Handle Problem Language Result Execution time Memory
481744 2021-10-21T14:34:06 Z mehdi_farhadian Job Scheduling (CEOI12_jobs) C++14
100 / 100
 339 ms 13764 KB 
#include <bits/stdc++.h>
#define pb push_back
#define endl '\n'
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O0")
#pragma GCC optimize("O1")
using namespace std;
typedef long long ll;

const int N = 1e6 + 10;
int n, d, m;
vector<pair<int, int>> vec;

bool check(int x)
{
    queue<int> q;
    int last = 0;
    for (int i = 1; i <= n; i++) {
        while (last < vec.size() && vec[last].first == i) {
            q.push(i);
            last++;
        }
        int cnt = 0;
        while (q.size() && cnt < x) {
            cnt++;
            int tmp = q.front();
            if (i - tmp > d) {
                return false;
            }
            q.pop();
        }
    }
    return q.size() == 0;
}

void print(int x)
{
    int ind = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < x && ind < vec.size(); j++) {
            cout << vec[ind].second << " ";
            ind++;
        }
        cout << 0 << endl;
    }
}

void solve()
{
    int l = -1, r = 1e6;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (check(m)) {
            r = m;
        }
        else {
            l = m;
        }
    }
    cout << r << endl;
    print(r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> d >> m;
    vec.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> vec[i].first;
        vec[i].second = i + 1;
    }
    sort(vec.begin(), vec.end());
    solve();
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while (last < vec.size() && vec[last].first == i) {
      |                ~~~~~^~~~~~~~~~~~
jobs.cpp: In function 'void print(int)':
jobs.cpp:41:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j < x && ind < vec.size(); j++) {
      |                                  ~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1808 KB Output is correct
2 Correct 34 ms 1816 KB Output is correct
3 Correct 34 ms 1840 KB Output is correct
4 Correct 35 ms 1820 KB Output is correct
5 Correct 35 ms 1748 KB Output is correct
6 Correct 35 ms 1792 KB Output is correct
7 Correct 35 ms 1744 KB Output is correct
8 Correct 36 ms 1804 KB Output is correct
9 Correct 49 ms 1876 KB Output is correct
10 Correct 50 ms 1932 KB Output is correct
11 Correct 39 ms 1612 KB Output is correct
12 Correct 77 ms 3152 KB Output is correct
13 Correct 125 ms 4604 KB Output is correct
14 Correct 165 ms 6264 KB Output is correct
15 Correct 191 ms 7512 KB Output is correct
16 Correct 244 ms 9112 KB Output is correct
17 Correct 282 ms 10564 KB Output is correct
18 Correct 304 ms 12128 KB Output is correct
19 Correct 339 ms 13764 KB Output is correct
20 Correct 274 ms 10560 KB Output is correct