oj.uz

Submission #95431

# Submission time Handle Problem Language Result Execution time Memory
95431 2019-02-01T07:07:20 Z forestryks Job Scheduling (CEOI12_jobs) C++14
55 / 100
 36 ms 8312 KB 
///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
////////////////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 1e5 + 5;
int n, d, m;
vector<int> a[MAXN];
int t[MAXN];

bool check(int cnt, bool pr) {
    if (pr) cout << cnt << '\n';

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        for (auto it : a[i]) {
            q.push(it);
        }

        for (int j = 0; j < cnt && !q.empty(); ++j) {
            int x = q.front();
            q.pop();
            if (i > t[x] + d) return false;
            if (pr) cout << x + 1 << ' ';
        }
        if (pr) cout << "0\n";
    }

    if (q.empty()) return true;
    return false;
}

int main() {
    FAST_IO;
    cin >> n >> d >> m;
    rep(i, m) {
        cin >> t[i];
        t[i]--;
        a[t[i]].push_back(i);
    }

    int l = 0, r = m;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (check(m, false)) {
            r = m;
        } else {
            l = m;
        }
    }

    check(r, true);
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4748 KB Output is correct
2 Correct 30 ms 4948 KB Output is correct
3 Correct 31 ms 4812 KB Output is correct
4 Correct 31 ms 4784 KB Output is correct
5 Correct 31 ms 4820 KB Output is correct
6 Correct 29 ms 4816 KB Output is correct
7 Correct 29 ms 4820 KB Output is correct
8 Correct 29 ms 4820 KB Output is correct
9 Correct 36 ms 4728 KB Output is correct
10 Correct 33 ms 4732 KB Output is correct
11 Correct 32 ms 4600 KB Output is correct
12 Runtime error 17 ms 7672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 18 ms 7800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 23 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 7800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 23 ms 8184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 24 ms 8312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 17 ms 7800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 17 ms 7648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 23 ms 8312 KB Execution killed with signal 11 (could be triggered by violating memory limits)