oj.uz

답안 #474267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474267 2021-09-17T17:04:01 Z satyam_G Job Scheduling (CEOI12_jobs) C++14
100 / 100
 335 ms 13700 KB 
#include <bits/stdc++.h>
using namespace std;

#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define cout_vec(a) for(auto q : a) cout << q << " "; cout << "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
#define t_cases int t; cin >> t; while(t--)
#define debug(a) cout << a << "\n"

using intl = long long;
using vi = vector<int>;
using vd = vector<double>;
using vil = vector<intl>;
using pi = pair<int, int>;
using pil = pair<intl, intl>;
using vpi = vector<pair<int, int>>;
using vpil = vector<pair<intl, intl>>;

const intl MOD = 1000000007;
const intl MAXL = 50000;

bool is_pos(vector<pair<int, int>> &a, int n, int d, int nm) {

    int i = 0, j = 0, day;

    for (day = 1; day <= n; day++) {

        while (j < a.size() and j - i + 1 <= nm and a[j].fi <= day) {
            j++;
        }

        while (i < j) {
            if (day - a[i].fi > d) return false;
            i++;
        }

    }

    if (i < n) return false;

    return true;

}


void solve() {

    int n, d, m; cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    repi(m) {
        cin >> a[i].fi;
        a[i].se = i;
    }

    sort(a.begin(), a.end());

    int s = 1, e = 1000000000, ans = -1;

    while (s <= e) {

        int mid = s + (e - s) / 2;

        if (is_pos(a, n, d, mid)) {
            ans = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }

    cout << ans << "\n";

    int i = 0, j = 0, day;

    for (day = 1; day <= n; day++) {

        while (j < a.size() and j - i + 1 <= ans and a[j].fi <= day) {
            j++;
        }

        while (i < j) {
            cout << a[i].se + 1 << " ";
            i++;
        }

        cout << "0\n";

    }



}

int main() {

    FAST;

//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif

    // freopen("socdist.in", "r", stdin);
    // freopen("socdist.out", "w", stdout);

    // t_cases solve();
    solve();

}

Compilation message

jobs.cpp: In function 'bool is_pos(std::vector<std::pair<int, int> >&, int, int, int)':
jobs.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while (j < a.size() and j - i + 1 <= nm and a[j].fi <= day) {
      |                ~~^~~~~~~~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (j < a.size() and j - i + 1 <= ans and a[j].fi <= day) {
      |                ~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 1612 KB Output is correct
2 Correct 27 ms 1628 KB Output is correct
3 Correct 27 ms 1624 KB Output is correct
4 Correct 27 ms 1628 KB Output is correct
5 Correct 27 ms 1600 KB Output is correct
6 Correct 27 ms 1616 KB Output is correct
7 Correct 30 ms 1624 KB Output is correct
8 Correct 34 ms 1696 KB Output is correct
9 Correct 42 ms 1856 KB Output is correct
10 Correct 42 ms 1856 KB Output is correct
11 Correct 40 ms 1672 KB Output is correct
12 Correct 69 ms 3168 KB Output is correct
13 Correct 103 ms 4588 KB Output is correct
14 Correct 161 ms 6140 KB Output is correct
15 Correct 171 ms 7544 KB Output is correct
16 Correct 251 ms 9108 KB Output is correct
17 Correct 254 ms 10544 KB Output is correct
18 Correct 289 ms 12100 KB Output is correct
19 Correct 335 ms 13700 KB Output is correct
20 Correct 255 ms 10608 KB Output is correct