QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180052 | #6416. Classical Scheduling Problem | jackwas | WA | 108ms | 7672kb | C++14 | 5.0kb | 2023-09-15 15:06:57 | 2023-09-15 15:06:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> 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 (ll i = j; i < n; i++)
#define forn(i, n) for (ll i = 0; i < n; i++)
#define forn1(i, n) for (ll i = 1; i <= n; i++)
#define fornrb(i, j, n) for (ll i = n - 1; i >= j; i--)
#define fornb(i, n) for (ll i = n - 1; i >= 0; i--)
#define forn1b(i, n) for (i = n; i > 0; i--)
#define fornn(i, n) for (ll 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 ll IMX = 2e9 + 5;
const ll LMX = 4e18 + 10, MOD = 1e9 + 7, MOD2 = 998244353;
const ll MAXN = 2e5 + 5;
ll n, b[MAXN];
ll t, a[MAXN];
bool comp(ll _a, ll _b) {
if (b[_a] != b[_b]) return b[_a] < b[_b];
return _a < _b;
// return a[_a] < a[_b];
}
struct cmp {
bool operator() (ll _a, ll _b) {
if (a[_a] != a[_b]) return a[_a] > a[_b];
return _a < _b;
// return b[_a] > b[_b];
}
};
struct rev {
bool operator() (ll _a, ll _b) {
if (a[_a] != a[_b]) return a[_a] < a[_b];
return _a < _b;
//return b[_a] > b[_b];
}
};
ll sorted[MAXN], pos[MAXN];
ll test(ll k) {
prqu<ll, vector<ll>, rev> qk, qm;
prqu<ll, vector<ll>, cmp> qt;
ll m = 0;
ll sum = 0;
forn(i, n) {
qt.push(i);
pos[i] = 2;
}
assert(qt.size() == n);
ll ms = 0; // expected size of qm
ll idx = 0;
for (m = k; m <= n; m++, ms++) {
if (idx == n) break;
for (; idx < n && b[sorted[idx]] <= m; idx++) {
ll cur = sorted[idx];
qk.push(cur);
if (pos[cur] == 1) ms++;
else sum += a[cur];
pos[cur] = 0;
}
while (!qm.empty() && pos[qm.top()] != 1) {
qm.pop();
ms--;
}
for (; qk.size() > k; ) {
if (qm.size() < ms) {
qm.push(qk.top());
pos[qk.top()] = 1;
} else if (!qm.empty() && a[qk.top()] < a[qm.top()]) {
qm.push(qk.top());
pos[qk.top()] = 1;
} else {
qt.push(qk.top());
sum -= a[qk.top()];
pos[qk.top()] = 2;
}
qk.pop();
}
while (qm.size() > ms) {
if (pos[qm.top()] != 1) {
qm.pop();
ms--;
} else {
qt.push(qm.top());
pos[qm.top()] = 2;
sum -= a[qm.top()];
qm.pop();
}
}
while (!qt.empty()) {
if (pos[qt.top()] != 2) {
qt.pop();
continue;
}
while (qm.size() && pos[qm.top()] != 1) {
qm.pop();
ms--;
}
if (!qm.empty() && a[qt.top()] < a[qm.top()]) {
sum += a[qt.top()] - a[qm.top()];
pos[qt.top()] = 1;
pos[qm.top()] = 2;
ll qm1 = qm.top(), qt1 = qt.top();
qt.pop();
qm.pop();
qt.push(qm1);
qm.push(qt1);
} else {
break;
}
}
if (qk.size() == k && sum <= t && qm.size() == ms) {
return m;
}
}
return 0;
}
vector<ll> ret;
void getSolution(ll k, ll m) {
prqu<ll, vector<ll>, rev> qk, qm;
forn(i, n) {
if (b[i] <= m) qk.push(i);
else qm.push(i);
}
while (qk.size() > k) {
qm.push(qk.top());
qk.pop();
}
while (qm.size() > m - k) qm.pop();
while (!qm.empty()) {
ret.pb(qm.top() + 1);
qm.pop();
}
while (!qk.empty()) {
ret.pb(qk.top() + 1);
qk.pop();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll q;
cin >> q;
while(q--) {
cin >> n >> t;
forn(i, n) {
cin >> a[i] >> b[i];
sorted[i] = i;
}
sort(sorted, sorted + n, comp);
ll l = 0, r = n;
ll saved = 0;
vector<ll> vsaved(n + 1);
while (l < r) {
ll k = (l + r + 1) / 2, m = test(k);
if (m) {
l = k;
saved = m;
vsaved[k] = m;
}
else r = k - 1;
}
cout << l el << vsaved[l] el;
ret.clear();
getSolution(l, vsaved[l]);
sort(ret.begin(), ret.end());
forn(i, vsaved[l]) cout << ret[i] spe;
cout el;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7540kb
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: 108ms
memory: 7672kb
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 3 9 12 14 15 16 18 21 53 53 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 12 12 1 2 4 5 6 7 8 12 13 14 15 16 0 0 10 10 5 7 9 10 12 15 19 22 28 29 0 0 10 11 1 2 4 5 6 7 8 9 11 12 13 0 0 ...
result:
wrong answer jury has a better answer: jans = 7, pans = 0 (test case 4)