Submission #1314144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314144		amloxg	Minerals (JOI19_minerals)	C++20	80 / 100	21 ms	2768 KiB

minerals

#include "minerals.h"
#include <vector>
#include <iostream>

using namespace std;

int same_num = 0;

void subSolve(vector<int>& X, vector<int>& Y, bool is_X){
    if (X.size() <= 1) Answer(X[0], Y[0]);
    else{
        vector<int> new_X1, new_Y1, new_X2, new_Y2;
        for (int i = 0; i < X.size()/2; ++i) new_X1.push_back(X[i]);
        for (int i = X.size()/2; i < X.size(); ++i) new_X2.push_back(X[i]);
        if (is_X) for (auto x2 : new_X2) same_num = Query(x2);
        else for (auto x1 : new_X1) same_num = Query(x1);

        for (auto y : Y){
            int query = Query(y);
            if (query == same_num) new_Y1.push_back(y);
            else{
                new_Y2.push_back(y);
                same_num = query;
            }
        }
        subSolve(new_X1, new_Y1, true);
        subSolve(new_X2, new_Y2, false);
    }
}

void Solve(int N){
    vector<int> X, Y;
    for (int i = 1; i <= 2*N; ++i)
        if (Query(i) != same_num){
            X.push_back(i);
            ++same_num;
        }
        else Y.push_back(i);
    subSolve(X, Y, true);
}

• 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