Submission #1170191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170191		pythontest	Minerals (JOI19_minerals)	C++20	90 / 100	19 ms	2708 KiB

minerals

#include "minerals.h"
#include <vector>
#include <iostream>
std::vector<int> z1;
std::vector<int> z2;
std::vector<int> zmapowane;
int lastop=0;
int QProxy(int a){
    return lastop= Query(a);
}
void reksolve(int tl, int tr, std::vector<int> can,bool odw){
    std::vector<int> lewi,prawi;
    if(tl==tr) {
        zmapowane[tl]=can[0];
        return;
    }
    int tm=(tl+tr)/2;
    if(!odw) for(int i=tm+1;i<=tr;i++)
        QProxy(z1[i]);
    else for(int i=tl;i<=tm;i++)
        QProxy(z1[i]);
    for(auto x: can){
        int prev=lastop;
        if(lewi.size()==tm-tl+1){
            prawi.push_back(x);
        }
        else if(prawi.size()==tr-tm){
            lewi.push_back(x);
        }
        else{
            int res = QProxy(x);
            if(prev==res)
                lewi.push_back(x);
            else
                prawi.push_back(x);
        }
    }
    reksolve(tl,tm,lewi,false);
    reksolve(tm+1,tr,prawi,true);
}
void Solve(int N) {
    int lastv=0;
    zmapowane.resize(N);
    for(int i=1;i<=2*N;i++){
        int ans = QProxy(i);
        if(ans==lastv) z2.push_back(i);
        else z1.push_back(i);
        lastv=ans;
    }
    reksolve(0,N-1,z2,false);
    for(int i=0;i<N;i++){
        Answer(zmapowane[i],z1[i]);
    }
}

• 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