Submission #719764

#	Time	Username	Problem	Language	Result	Execution time	Memory
719764		walterw	Minerals (JOI19_minerals)	C++17	80 / 100	50 ms	3424 KiB

minerals

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

using namespace std;

int pre, cur;

void dnc(vector<int> x, vector<int> y, bool bx = true, bool by = true) {
    if (x.size() == 1) {

        Answer(x[0], y[0]);
        return;
    }


    int n = x.size(); int mid = n / 2;

    vector<int> x1, x2;

    for (int i = 0; i < mid; i++) x1.push_back(x[i]);
    for (int i = mid; i < n; i++) x2.push_back(x[i]);

    if (bx) {
        for (int i = mid; i < n; i++) {
            cur = Query(x[i]);
            swap(pre, cur);
        }
    } else {
        for (int i = 0; i < mid; i++) {
            cur = Query(x[i]);
            swap(pre, cur);
        }
    }


    vector<int> v1, v2;

    for (auto c : y) {
        cur = Query(c);
        swap(pre, cur);
        if (pre != cur) {
            v1.push_back(c);
        } else {
            v2.push_back(c);
        }
    }

    dnc(x1, v2, true, !by);
    dnc(x2, v1, false, !by);
}

void Solve(int N) {

    vector<int> v1, v2;

    for (int i = 1; i <= 2 * N; ++i) {
        cur = Query(i);
        swap(cur, pre);
        if (cur != pre) {
            v1.push_back(i);
        } else {
            v2.push_back(i);
        }
    }


    dnc(v1, v2);
}

• 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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10