oj.uz

Submission #49187

# Submission time Handle Problem Language Result Execution time Memory
49187 2018-05-23T13:05:27 Z Benq Job Scheduling (CEOI12_jobs) C++14
40 / 100
 387 ms 24220 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

vi todo[MX], ans[MX];
int N, D, M;

int gen(int x, bool b = 0) {
    // return 0;
    queue<pi> cur;
    int mx = 0;
    FOR(i,1,N+1) {
        for (int j: todo[i]) cur.push({j,i});
        for (int j = 0; j < x && sz(cur) > 0; ++j) {
            if (b) ans[i].pb(cur.front().f); 
            mx = max(mx,cur.front().s-i);
            cur.pop();
        }
    }
    if (sz(cur)) return MOD;
    return mx;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> D >> M;
    FOR(i,1,M+1) {
        int x; cin >> x;
        todo[x].pb(i);
    }
    int lo = 1, hi = 1000000;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (gen(mid) <= D) hi = mid;
        else lo = mid+1;
    }
    gen(lo,1);
    cout << lo << "\n";
    FOR(i,1,N+1) {
        for (int j: ans[i]) cout << j << " ";
        cout << "0\n";
    }
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 7236 KB Output isn't correct
2 Incorrect 48 ms 7352 KB Output isn't correct
3 Incorrect 47 ms 7352 KB Output isn't correct
4 Incorrect 45 ms 7352 KB Output isn't correct
5 Incorrect 46 ms 7352 KB Output isn't correct
6 Incorrect 44 ms 7352 KB Output isn't correct
7 Incorrect 45 ms 7368 KB Output isn't correct
8 Incorrect 50 ms 7412 KB Output isn't correct
9 Incorrect 89 ms 10084 KB Output isn't correct
10 Incorrect 65 ms 10084 KB Output isn't correct
11 Correct 50 ms 10084 KB Output is correct
12 Correct 93 ms 10084 KB Output is correct
13 Correct 132 ms 11720 KB Output is correct
14 Correct 267 ms 14528 KB Output is correct
15 Correct 198 ms 14528 KB Output is correct
16 Correct 314 ms 16196 KB Output is correct
17 Correct 372 ms 20792 KB Output is correct
18 Incorrect 318 ms 21044 KB Output isn't correct
19 Incorrect 387 ms 24220 KB Output isn't correct
20 Correct 381 ms 24220 KB Output is correct