QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180066 | #6416. Classical Scheduling Problem | jackwas | WA | 0ms | 7672kb | C++14 | 5.1kb | 2023-09-15 15:16:49 | 2023-09-15 15:16:49 |
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;
// }
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()]) {
ll qm1 = qm.top(), qt1 = qt.top();
sum += a[qt1] - a[qm1];
qt.pop();
qm.pop();
qt.push(qm1);
qm.push(qt1);
pos[qt1] = 1;
pos[qm1] = 2;
} 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: 0
Wrong Answer
time: 0ms
memory: 7672kb
input:
2 4 100 20 1 40 4 60 3 30 3 1 5 10 1
output:
1 1 1 0 0
result:
wrong answer jury has a better answer: jans = 2, pans = 1 (test case 1)