QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179953#6417. Classical Summation ProblemjackwasWA 1ms3572kbC++144.6kb2023-09-15 13:53:312023-09-15 13:53:31

Judging History

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

  • [2023-09-15 13:53:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3572kb
  • [2023-09-15 13:53:31]
  • 提交

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;
    int m = 0;
    ll sum = 0;
    // put everything into st;
    forn(i, n) st.insert(i);
    int idx = 0;

    for (m = k; m <= n; m++) {
        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(it);
                sum -= a[cur];
            } else {
                st.erase(cur);
            }
        }
        while (sk.size() > k) {
            int cur = *(sk.begin());
            sk.erase(sk.begin());
            sm.insert(cur);
        }
        while (sm.size() < (m - k)) {
            //if (st.empty()) break;
            assert(!st.empty() && "st.empty() expectedly");
            sum += a[*(st.begin())];  // SEGTERM
            sm.insert(*(st.begin()));
            st.erase(st.begin());
        }
        while (sm.size() > (m - k)) {
            int cur = *(sm.begin());
            sum -= a[cur];
            sm.erase(sm.begin());
            st.insert(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(sm.begin());
            st.erase(st.begin());
            sm.insert(st1);
            st.insert(sm1);
        }
        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: 0
Wrong Answer
time: 1ms
memory: 3572kb

input:

3 2

output:

1
1
1
1
1
1
1
1
1

result:

wrong answer 1st numbers differ - expected: '14', found: '1'