QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180000 | #6416. Classical Scheduling Problem | jackwas | RE | 0ms | 3640kb | C++14 | 4.9kb | 2023-09-15 14:25:30 | 2023-09-15 14:25:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define el << '\n'
#define spe << ' '
#define sp spe <<
#define umap unordered_map
#define uset unordered_set
#define prqu priority_queue
#define fornr(i, j, n) for (int i = j; i < n; i++)
#define forn(i, n) for (int i = 0; i < n; i++)
#define forn1(i, n) for (int i = 1; i <= n; i++)
#define fornrb(i, j, n) for (int i = n - 1; i >= j; i--)
#define fornb(i, n) for (int i = n - 1; i >= 0; i--)
#define forn1b(i, n) for (i = n; i > 0; i--)
#define fornn(i, n) for (int i = 1; i <= n; i++)
#define rety cout << "YES\n"; return 0;
#define retn cout << "NO\n"; return 0;
#define conty cout << "YES\n"; continue;
#define contn cout << "NO\n"; continue;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
const int IMX = 2e9 + 5;
const ll LMX = 4e18 + 10, MOD = 1e9 + 7, MOD2 = 998244353;
const int MAXN = 2e5 + 5;
int n, b[MAXN];
ll t, a[MAXN];
int sorted[MAXN];
struct cmp {
bool operator() (int _a, int _b) {
if (a[_a] != a[_b]) return a[_a] > a[_b];
return b[_a] > b[_b];
}
};
struct rev {
bool operator() (int _a, int _b) {
if (a[_a] != a[_b]) return a[_a] < a[_b];
return b[_a] > b[_b];
}
};
int test(int k) {
set<int, cmp> sk, sm;
set<int, rev> st;
ll sum = 0;
forn(i, n) st.insert(i); // put everything into st;
int idx = 0;
for (int m = k; m <= n; m++) {
if (idx == n) break;
for (; idx < n && b[sorted[idx]] <= m; idx++) {
ll cur = sorted[idx];
sk.insert(cur);
sum += a[cur];
set<int, cmp>::iterator it = sm.find(cur);
if (it != sm.end()) {
sm.erase(cur); // sm.erase(it);
sum -= a[cur];
} else {
st.erase(cur);
}
}
while (sk.size() > k) {
int cur = *(sk.begin());
sk.erase(cur); // sk.erase(sk.begin());
sm.insert(cur);
}
while (sm.size() > (m - k)) {
int cur = *(sm.begin());
sum -= a[cur];
sm.erase(cur); // sm.erase(sm.begin());
st.insert(cur);
}
while (sm.size() < (m - k)) {
if (st.empty()) {
//cout << k sp m sp sm.size() sp sk.size() sp n el;
break;
}
// assert(!st.empty() && "st.empty() expectedly");
int cur = *(st.begin());
sum += a[cur]; // SEGTERM
sm.insert(cur); // sm.insert(*(st.begin()));
st.erase(cur);
}
while (!st.empty() && !sm.empty() && a[*st.begin()] < a[*sm.begin()]) {
// swap
int sm1 = *(sm.begin());
int st1 = *(st.begin());
sum -= a[sm1];
sum += a[st1];
sm.erase(sm1); // sm.erase(sm.begin());
st.erase(st1); // st.erase(st.begin());
sm.insert(st1);
st.insert(sm1);
}
assert((sm.size() + st.size() + sk.size() == n) && "someting wrong");
if (sk.size() == k && sum <= t) {
assert(sm.size() == (m - k) && "sm.size() wrong");
return m;
}
}
return 0;
}
vector<ll> ret;
void getSolution(ll k, ll m) {
set<int, cmp> sk, sm;
forn(i, n) {
if (b[i] <= m) sk.insert(i);
else sm.insert(i);
}
while (sk.size() > k) {
int cur = *sk.begin();
sk.erase(sk.begin());
sm.insert(cur);
}
while (sm.size() > (m - k)) {
sm.erase(sm.begin());
}
while (!sm.empty()) {
ret.pb((*sm.begin()) + 1);
sm.erase(sm.begin());
}
while (!sk.empty()) {
ret.pb((*sk.begin()) + 1);
sk.erase(sk.begin());
}
}
bool comp(ll _a, ll _b) {
if (b[_a] != b[_b]) return b[_a] < b[_b];
return a[_a] < a[_b];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while(q--) {
cin >> n >> t;
forn(i, n) {
cin >> a[i] >> b[i];
sorted[i] = i;
}
sort(sorted, sorted + n, comp);
int l = 0, r = n;
vector<ll> vsaved(n + 1);
while (l < r) {
ll k = (l + r + 1) / 2, m = test(k);
if (m) {
l = k;
vsaved[k] = m;
}
else r = k - 1;
}
cout << l el << vsaved[l] el;
ret.clear();
if (vsaved[l] > 0) {
getSolution(l, vsaved[l]);
assert(ret.size() == vsaved[l] && "getSolution wrong");
sort(ret.begin(), ret.end());
forn(i, vsaved[l] - 1) cout << ret[i] spe;
cout << ret[vsaved[l] - 1] el;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
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
Runtime Error
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...