# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
61857 | 2018-07-26T23:29:59 Z | qkxwsm | Job Scheduling (CEOI12_jobs) | C++17 | 456 ms | 33792 KB |
/* PROG: source LANG: C++11 _____ .' '. / 0 0 \ | ^ | | \ / | \ '---' / '._____.' */ #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; struct chash { int operator()(int x) const { x ^= (x >> 20) ^ (x >> 12); return x ^ (x >> 7) ^ (x >> 4); } int operator()(long long x) const { return x ^ (x >> 32); } }; template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using hashtable = gp_hash_table<T, T, chash>; template<class T> void readi(T &x) { T input = 0; bool negative = false; char c = ' '; while (c < '-') { c = getchar(); } if (c == '-') { negative = true; c = getchar(); } while (c >= '0') { input = input * 10 + (c - '0'); c = getchar(); } if (negative) { input = -input; } x = input; } template<class T> void printi(T output) { if (output == 0) { putchar('0'); return; } if (output < 0) { putchar('-'); output = -output; } int aout[20]; int ilen = 0; while(output) { aout[ilen] = ((output % 10)); output /= 10; ilen++; } for (int i = ilen - 1; i >= 0; i--) { putchar(aout[i] + '0'); } return; } template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template<class T> T normalize(T x, T mod = 1000000007) { return (((x % mod) + mod) % mod); } long long randomizell(long long mod) { return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod; } int randomize(int mod) { return ((1ll << 15) * rand() + rand()) % mod; } #define y0 ___y0 #define y1 ___y1 #define MP make_pair #define MT make_tuple #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fi first #define se second #define debug(x) cerr << #x << " = " << x << endl; const long double PI = 4.0 * atan(1.0); const long double EPS = 1e-10; #define MAGIC 347 #define SINF 10007 #define CO 1000007 #define INF 1000000007 #define BIG 1000000931 #define LARGE 1696969696967ll #define GIANT 2564008813937411ll #define LLINF 2696969696969696969ll #define MAXN 1000013 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pdd; int N, D, M; pii arr[MAXN]; vector<int> go[MAXN / 10]; bool solve(int x) { for (int i = 0; i < N; i++) { go[i].clear(); } int iter = 0; for (int i = 0; i < N; i++) { if (iter < M && arr[iter].fi < i - D) { return false; } int j; for (j = iter; j < iter + x && j < M && arr[j].fi <= i; j++) { go[i].PB(arr[j].se); } iter = j; } return (iter == M); } int32_t main() { ios_base::sync_with_stdio(0); srand(time(0)); // cout << fixed << setprecision(10); // cerr << fixed << setprecision(10); if (fopen("input.in", "r")) { freopen ("input.in", "r", stdin); freopen ("output.out", "w", stdout); } cin >> N >> D >> M; for (int i = 0; i < M; i++) { int x; cin >> x; x--; arr[i] = MP(x, i); } sort(arr, arr + M); int lo = 0, hi = M; while(hi > lo) { int mid = (lo + hi) / 2; if (solve(mid)) { hi = mid; } else { lo = mid + 1; } } solve(lo); cout << lo << '\n'; for (int i = 0; i < N; i++) { for (int x : go[i]) { cout << x + 1 << ' '; } cout << "0\n"; } // cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 4852 KB | Output is correct |
2 | Correct | 38 ms | 5272 KB | Output is correct |
3 | Correct | 44 ms | 5604 KB | Output is correct |
4 | Correct | 35 ms | 6060 KB | Output is correct |
5 | Correct | 54 ms | 6568 KB | Output is correct |
6 | Correct | 58 ms | 6688 KB | Output is correct |
7 | Correct | 40 ms | 6944 KB | Output is correct |
8 | Correct | 35 ms | 7240 KB | Output is correct |
9 | Correct | 50 ms | 7668 KB | Output is correct |
10 | Correct | 55 ms | 8184 KB | Output is correct |
11 | Correct | 44 ms | 8308 KB | Output is correct |
12 | Correct | 89 ms | 10868 KB | Output is correct |
13 | Correct | 125 ms | 14620 KB | Output is correct |
14 | Correct | 268 ms | 18684 KB | Output is correct |
15 | Correct | 209 ms | 22076 KB | Output is correct |
16 | Correct | 305 ms | 27172 KB | Output is correct |
17 | Runtime error | 342 ms | 33792 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
18 | Runtime error | 399 ms | 33792 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
19 | Runtime error | 456 ms | 33792 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
20 | Runtime error | 312 ms | 33792 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |