QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176000 | #6416. Classical Scheduling Problem | danielkou5855 | WA | 460ms | 3932kb | C++17 | 3.2kb | 2023-09-11 07:21:32 | 2023-09-11 07:21:32 |
Judging History
answer
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<pair<int, int>, int> mmap;
bool cmp_second(const pair<int, int> &a, const pair<int, int> &b) {
return a.second < b.second;
}
bool cmp_first(const pair<int, int> &a, const pair<int, int> &b) {
if (a.first == b.first) {
return mmap[a] < mmap[b];
}
return a.first < b.first;
}
pair<bool, int> works(int m, vector<pair<int, int>> &arr, int smax) {
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp_first)> small(cmp_first), big(cmp_first);
if (smax == 0) {
return make_pair(true, -1);
}
vector<int> dp((int) arr.size());
int running = 0;
for (int i = (int) arr.size() - 1; i >= 0; i--) {
dp[i] = running;
big.push(arr[i]);
running += arr[i].first;
while ((int) big.size() > max(0LL, ((i == 0 ? 0 : arr[i - 1].second) - m))) {
cerr << big.top().first << endl;
running -= big.top().first; big.pop();
}
}
// cout << m << "\n";
// for (int i = 0; i < (int) dp.size(); i++) {
// cout << dp[i] << " ";
// }
// cout << "\n";
int running2 = 0; // less than
for (int i = 0; i < (int) arr.size(); i++) {
if ((i + 1 >= m) && (running2 + dp[i] + arr[i].first <= smax) && (max(0LL, arr[i].second - m) + i < (int) arr.size())) {
return {true, i};
}
small.push(arr[i]);
running2 += arr[i].first;
while ((int) small.size() >= m) {
running2 -= small.top().first; small.pop();
}
}
return {false, -1};
}
void print_ans(int ans, int m, vector<pair<int, int>> &arr) {
cout << m << "\n";
cout << (ans == -1 ? 0 : m + max(0LL, arr[ans].second - m)) << "\n";
if (ans == -1) {
return;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp_first)> small(cmp_first), big(cmp_first);
for (int i = 0; i < ans; i++) {
small.push(arr[i]);
while ((int) small.size() >= m) {
small.pop();
}
}
vector<int> p;
while (!small.empty()) {
cout << (mmap[small.top()] + 1) << " "; small.pop();
}
for (int i = (int) arr.size() - 2; i >= ans; i--) { // so i don't have to commit a war crime like in bsearch validation functoin
big.push(arr[i + 1]);
while ((int) big.size() > max(0LL, arr[i].second - m)) {
big.pop();
}
}
while (!big.empty()) {
cout << (mmap[big.top()] + 1) << " "; big.pop();
}
cout << (mmap[arr[ans]] + 1) << "\n";
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int T; cin >> T;
while (T--) {
int N, M; cin >> N >> M;
vector<pair<int, int>> arr(N); // a, b
mmap.clear();
for (int i = 0; i < N; i++) {
cin >> arr[i].first >> arr[i].second;
mmap[arr[i]] = i;
}
sort(arr.begin(), arr.end(), cmp_second);
// for (auto p : arr) {
// cout << p.first << " " << p.second << "\n";
// }
int l = 0, r = N;
int ans = -1;
while (l < r) {
int m = l + (r - l + 1) / 2;
auto asdkljasdlfasd = works(m, arr, M);
if (asdkljasdlfasd.first) {
l = m; ans = asdkljasdlfasd.second;
} else {
r = m - 1;
}
}
print_ans(ans, r, arr);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
2 4 100 20 1 40 4 60 3 30 3 1 5 10 1
output:
2 3 1 2 4 0 0
result:
ok ok, 2 test cases (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 460ms
memory: 3932kb
input:
10000 21 1892 174 13 604 15 170 2 413 11 899 2 531 12 651 17 553 9 429 8 837 14 937 12 577 7 532 11 19 2 173 10 165 6 762 15 221 6 945 13 302 19 7 3 54 26066 812 31 432 24 240 37 171 39 204 47 174 30 569 1 467 5 624 42 734 35 907 3 568 23 802 40 991 32 119 13 187 27 739 42 891 14 550 44 374 16 483 1...
output:
7 8 12 18 3 16 14 21 15 9 53 53 14 11 50 18 23 32 1 13 39 45 40 17 49 24 10 47 46 36 33 53 9 26 7 12 34 19 52 21 30 8 2 20 35 51 44 43 42 38 3 31 5 54 16 48 6 4 27 15 41 37 25 22 29 12 12 9 2 15 7 8 1 6 4 14 12 5 13 7 14 1 13 14 41 8 40 33 43 11 24 37 21 38 28 10 10 22 28 5 19 29 10 9 12 7 15 0 0 10...
result:
wrong answer topic 8 learned more than once (test case 65)