QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#208042 | #6416. Classical Scheduling Problem | duckier | WA | 1ms | 5656kb | C++14 | 2.9kb | 2023-10-09 04:14:11 | 2023-10-09 04:14:11 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int a;
int b;
int idx;
};
const int MAXN = 2e5 + 5;
int q, n, t, tot;
node topics[MAXN], sorted[MAXN];
auto cmp2 = [](int i1, int i2) { return topics[i1].a < topics[i2].a; };
set<int, decltype(cmp2)> usedl(cmp2), unusedl(cmp2), usedr(cmp2), unusedr(cmp2);
bool cmp(node n1, node n2) {
if (n1.b == n2.b) {
return n1.a < n2.a;
}
return n1.b < n2.b;
}
bool incm() {
if (unusedr.empty()) {
return false;
}
int minuu = *(unusedr.begin());
tot += topics[minuu].a;
usedr.insert(minuu);
unusedr.erase(minuu);
return true;
}
bool add(int x) {
unusedl.insert(x);
int maxu = *usedl.rbegin(), minuu = *unusedl.begin();
if (topics[maxu].a > topics[minuu].a) {
//replace with cheaper option
usedl.insert(minuu);
unusedl.erase(minuu);
usedl.erase(maxu);
unusedl.insert(maxu);
tot += topics[minuu].a - topics[maxu].a;
}
//process right side
if (usedr.find(x) != usedr.end()) {
//is using this one
usedr.erase(x);
if (unusedr.empty()) {
return false;
}
int minuu = *unusedr.begin();
usedr.insert(minuu);
unusedr.erase(minuu);
}
else {
unusedr.erase(x);
}
return true;
}
bool test(int k) {
int s = max(k, sorted[k].b);
for (int i = 1; i <= s; i++) {
unusedl.insert(sorted[i].idx);
}
for (int i = 1; i <= k; i++) {
int minuu = *unusedl.begin();
usedl.insert(minuu);
unusedl.erase(minuu);
tot += topics[minuu].a;
}
for (int i = s + 1; i <= n; i++) {
unusedr.insert(sorted[i].idx);
}
int remaining = s - k;
for (int i = 1; i <= remaining; i++) {
if (unusedr.empty()) return false;
int minuu = *unusedr.begin();
usedr.insert(minuu);
unusedr.erase(minuu);
tot += topics[minuu].a;
}
if (tot <= t) return true;
int c = s;
for (int m = s; m <= n; m++) {
while (c < n && sorted[c + 1].b <= m) {
add(c + 1);
c++;
if (tot <= t) return true;
}
if (tot <= t) return true;
incm();
if (tot <= t) return true;
}
return false;
}
void reset() {
tot = 0;
usedl.clear();
unusedl.clear();
usedr.clear();
unusedr.clear();
}
signed main() {
cin >> q;
while (q--) {
cin >> n >> t;
reset();
for (int i = 1; i <= n; i++) {
int x, y;
cin >> topics[i].a >> topics[i].b;
topics[i].idx = i;
sorted[i] = topics[i];
}
sort(sorted + 1, sorted + n + 1, cmp);
int lo = 0, hi = n;
while (lo != hi) {
reset();
int mi = (lo + hi) / 2 + 1;
if (test(mi)) {
lo = mi;
}
else {
hi = mi - 1;
}
}
set<int> s;
for (auto i = usedl.begin(); i != usedl.end(); i++) {
s.insert(*i);
}
for (auto i = usedr.begin(); i != usedr.end(); i++) {
s.insert(*i);
}
cout << lo << '\n';
cout << s.size() << '\n';
for (auto i = s.begin(); i != s.end(); i++) {
cout << *i << ' ';
}
cout << '\n';
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5656kb
input:
2 4 100 20 1 40 4 60 3 30 3 1 5 10 1
output:
2 3 1 2 4 0 1 1
result:
wrong answer too much time taken to learn the topics: 10 > 5 (test case 2)