Submission #1127825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127825		Captain_Georgia	Minerals (JOI19_minerals)	C++20	25 / 100	18 ms	1368 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

void Solve (int N) {
    vector<int> low(2 * N + 1, 0), high(2 * N + 1), mid(2 * N + 1, -1);
    for (int i = 1;i <= N;i ++) {
        high[i + N] = N;
    }
    vector<int> index;
    for (int t = 0;t < 14;t ++) {
        vector<array<int, 2>> all;
        for (int i = N + 1;i <= N * 2;i ++) {
            mid[i] = (low[i] + high[i] + 1) / 2;
            all.push_back ({mid[i], i});
            // cout << i << " " << low[i] << " " << high[i] << "\n";
        } // cout << "\n";
        auto cmp = [&](array<int, 2> fi, array<int, 2> se) -> bool {
            return fi[0] > se[0];
        };
        sort (all.begin(), all.end(), cmp);
        int L = N + 1;
        for (int i = 0;i < all.size();i ++) {
            while (all[i][0] < L) {
                -- L;
                Query (L);
                index.push_back(L);
            }
            int tmp = Query (all[i][1]);
            if (tmp == N - all[i][0] + 2) {
                high[all[i][1]] = mid[all[i][1]] - 1;
            } else {
                low[all[i][1]] = mid[all[i][1]];
            }
            Query (all[i][1]);
        }
        while (index.size() > 0) Query (index.back()), index.pop_back();
    }
    for (int i = N + 1;i <= N * 2;i ++) {
        // cerr << high[i] << " " << i << "\n";
        Answer (low[i], i);
    }
}

/*

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6

*/

• Subtask 1: 0 / 6
• Subtask 2: 25 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10