QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180049#6416. Classical Scheduling ProblemjackwasWA 111ms7976kbC++145.0kb2023-09-15 15:03:382023-09-15 15:03:39

Judging History

你现在查看的是最新测评结果

  • [2023-09-15 15:03:39]
  • 评测
  • 测评结果:WA
  • 用时:111ms
  • 内存:7976kb
  • [2023-09-15 15:03:38]
  • 提交

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) {
    // cout << k el;
    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;
    }
    ll ms = 0;  // expected size of qm
    ll idx = 0;
    for (m = k; m <= n; m++, ms++) {
        while (idx < n && b[sorted[idx]] <= m) {
            ll cur = sorted[idx];
            qk.push(cur);
            if (pos[cur] == 1) ms++;
            else sum += a[cur];
            pos[cur] = 0;
            idx++;
        }

        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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7712kb

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: 111ms
memory: 7976kb

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)