Submission #542431

#	Time	Username	Problem	Language	Result	Execution time	Memory
542431		two_sides	Minerals (JOI19_minerals)	C++17	90 / 100	59 ms	4332 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>


namespace {
    using namespace std;

    const int N = 43005;

    int cost[N], best[N], cur = 0;

    mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

    void Prepare() {
        cost[2] = 2; best[2] = 1;
        for (int i = 3; i < N; i++) {
            int j = best[i - 1];
            if (cost[i - j - 1] + cost[j + 1] +
            j + 1 < cost[i - j] + cost[j] + j) j++;
            cost[i] = cost[i - j] + cost[j] + j + i;
            best[i] = j;
        }
    }

    void Split(vector<int> x, vector<int> y, bool f) {
        
        if (x.size() == 2) {
            cur = Query(x[f]);
            int nxt = Query(y[0]);
            if (cur != nxt) {
                Answer(x[0], y[0]);
                Answer(x[1], y[1]);
            } else {
                Answer(x[0], y[1]);
                Answer(x[1], y[0]);
            }
            cur = nxt; return;
        }
        if (x.size() == 1)
            return Answer(x[0], y[0]);
        int n = x.size(), len = ceil(0.36 * n);
        vector<int> nx[2], ny[2];
        for (int i = 0; i < len; i++) {
            nx[f ^ 1].push_back(x[i]);
            cur = Query(x[i]);
        }
        for (int i = len; i < n; i++)
            nx[f].push_back(x[i]);
        shuffle(y.begin(), y.end(), rng);
        for (int i = 0; i < n; i++) {
            if (nx[0].size() == ny[0].size()) {
                ny[1].push_back(y[i]); continue;
            }
            int nxt = Query(y[i]);
            if (cur != nxt)
                ny[1].push_back(y[i]);
            else ny[0].push_back(y[i]);
            cur = nxt;
        }
        Split(nx[0], ny[0], 0);
        Split(nx[1], ny[1], 1);
    }
}

void Solve(int n) {
    Prepare(); vector<int> x, y;
    for (int i = 1; i <= 2 * n; i++) {
        int nxt = Query(i);
        if (nxt != cur) x.push_back(i);
        else y.push_back(i);
        cur = nxt;
    }
    cerr<<cost[43000];
    Split(x, y, 0);
}

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