oj.uz

Submission #29084

# Submission time Handle Problem Language Result Execution time Memory
29084 2017-07-18T08:18:54 Z chpipis Job Scheduling (CEOI12_jobs) C++11
100 / 100
 403 ms 21044 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAX_M = 1e6 + 5;
const int MAX_N = 1e5 + 5;

int ar[MAX_M], n, d, m;
vi arrive[MAX_N], cont[MAX_N];

bool can(int k) {
    fill(cont, cont + n + 1, vi());
    deque<int> Q;
    int j = 0;
    for (int i = 1; i <= n - d; i++) {
        while (!Q.empty() && Q.front() < i) Q.pop_front();
        while (j < i + d) Q.pb(++j);
        for (auto it : arrive[i]) {
            if (Q.empty()) return false;
            int who = Q.front();
            cont[who].pb(it);
            if ((int)cont[who].size() >= k) Q.pop_front();
        }
    }
    return true;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    scanf("%d %d %d", &n, &d, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &ar[i]);
        arrive[ar[i]].pb(i);
    }
    int lo = 1, hi = m;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (can(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    can(hi);
    printf("%d\n", hi);
    for (int i = 1; i <= n; i++) {
        for (auto it : cont[i])
            printf("%d ", it);
        puts("0");
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:83:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &d, &m);
                                  ^
jobs.cpp:85:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
                            ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11976 KB Output is correct
2 Correct 29 ms 11976 KB Output is correct
3 Correct 29 ms 11976 KB Output is correct
4 Correct 26 ms 11976 KB Output is correct
5 Correct 29 ms 11976 KB Output is correct
6 Correct 36 ms 11976 KB Output is correct
7 Correct 33 ms 11976 KB Output is correct
8 Correct 23 ms 11976 KB Output is correct
9 Correct 46 ms 11968 KB Output is correct
10 Correct 49 ms 11992 KB Output is correct
11 Correct 29 ms 11672 KB Output is correct
12 Correct 59 ms 12728 KB Output is correct
13 Correct 96 ms 14840 KB Output is correct
14 Correct 216 ms 15896 KB Output is correct
15 Correct 203 ms 16292 KB Output is correct
16 Correct 256 ms 18140 KB Output is correct
17 Correct 376 ms 21044 KB Output is correct
18 Correct 249 ms 19064 KB Output is correct
19 Correct 283 ms 19064 KB Output is correct
20 Correct 403 ms 21044 KB Output is correct