| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 905055 | 2024-01-12T13:31:56 Z | akliu | Job Scheduling (CEOI12_jobs) | C++11 | 257 ms | 21240 KB |
#include <bits/stdc++.h>
using namespace std;
void fastio() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
void open(string filename) {
fastio();
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
typedef long long ll;
#define vll vector<ll>
#define vint vector<int>
#define vbool vector<bool>
#define vpii vector<pii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define ins(x) insert(x)
#define sz() size()
#define lb() lower_bound()
#define ub() upper_bound()
#define rsz resize
#define se second
#define fi first
#define cont continue
// scary demonic thing
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
struct g {
int day, n;
bool operator<(const g &y) {
if (day != y.day) return day < y.day;
return n < y.n; // Not necessary, compiler gives annoying error otherwise though
}
};
int N, D, M;
vector<g> v;
bool check(int m) {
// Iterate to check if the minimum is valid
int machines; // Using a multiset for machines is not necessary here because for the binary search we don't care about the values that we're storing. All we care about are the number of machines that are being used each day.
deque<int> q; // Note that q does NOT need to be sorted because we're pushing elements into q in chronological order. Therefore, the elements at the front of q will always be the ones that we need to check for the date limit violation.
int d = 0;
auto it = v.begin();
g val = *it;
while (d != N + 1) {
if (q.sz()) {
if (d - *(q.begin()) > D) {
return false;
}
}
machines = 0;
val = *it;
while (machines != m) {
if (!q.sz()) break;
++machines;
q.pop_front();
}
while (val.day == d) {
if (machines != m) ++machines;
else q.push_back(val.day);
++it;
if (it == v.end()) break;
val = *it;
}
++d;
}
return true;
}
void solve() {
// Input
cin >> N >> D >> M;
for (int i = 0; i < M; ++i) {
int a; cin >> a;
v.pb({a, i + 1});
}
sort(v.begin(), v.end());
// Binary search
int l = 1, r = 1e6, m;
while (l < r) {
m = (l + r) / 2;
if (check(m)) r = m;
else l = m + 1;
}
cout << l << "\n";
// Iterate once more with the correct minimum, very minor changes to the binary search algorithm to allow for storing the index of the value
vector<vint> ans(N + 1);
vector<int> machines;
deque<int> q;
int d = 0;
auto it = v.begin();
g val = *it;
while (d != N + 1) {
machines.clear();
val = *it;
while (machines.sz() != l) {
if (!q.sz()) break;
int valQ = *(q.begin());
machines.pb(valQ);
q.pop_front();
}
while (val.day == d) {
val = *it;
if (machines.sz() != l) {
machines.pb(val.n);
}
else q.push_back(val.n);
++it;
if (it == v.end()) break;
}
for (auto &x : machines) {
ans[d].pb(x);
}
++d;
}
// Output
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < ans[i].sz(); ++j) {
cout << ans[i][j] << " ";
}
cout << "0\n";
}
}
int main() {
fastio();
int tc = 1;
// cin >> tc;
while (tc--) {
solve();
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 26 ms | 3336 KB | Output is correct |
| 2 | Correct | 21 ms | 3032 KB | Output is correct |
| 3 | Correct | 21 ms | 3032 KB | Output is correct |
| 4 | Correct | 21 ms | 3032 KB | Output is correct |
| 5 | Correct | 21 ms | 3052 KB | Output is correct |
| 6 | Correct | 22 ms | 3028 KB | Output is correct |
| 7 | Correct | 21 ms | 2984 KB | Output is correct |
| 8 | Correct | 21 ms | 3024 KB | Output is correct |
| 9 | Correct | 31 ms | 4736 KB | Output is correct |
| 10 | Correct | 34 ms | 4704 KB | Output is correct |
| 11 | Correct | 25 ms | 2264 KB | Output is correct |
| 12 | Correct | 57 ms | 4300 KB | Output is correct |
| 13 | Correct | 78 ms | 8388 KB | Output is correct |
| 14 | Correct | 112 ms | 9084 KB | Output is correct |
| 15 | Correct | 127 ms | 9660 KB | Output is correct |
| 16 | Correct | 157 ms | 13440 KB | Output is correct |
| 17 | Correct | 193 ms | 17332 KB | Output is correct |
| 18 | Correct | 215 ms | 18176 KB | Output is correct |
| 19 | Correct | 257 ms | 21240 KB | Output is correct |
| 20 | Correct | 195 ms | 17844 KB | Output is correct |