Submission #824931

#	Time	Username	Problem	Language	Result	Execution time	Memory
824931		sunwukong123	Minerals (JOI19_minerals)	C++14	80 / 100	105 ms	5868 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std; 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
vector<int> v1,v2;
set<int> s1,s2;
set<int> s;
vector<pair<int,int>> out;
int lst;

bool has(int x){
    int q=Query(x);
    bool can=(lst==q);
    lst=q;
    return can;
}
void dnc(vector<int> L, vector<int> R){
    assert(L.size()==R.size());
    if(L.size() == 1 && R.size() == 1){
        out.push_back({L[0],R[0]});
        return;
    }
    int mi=(int)R.size()/2;
    vector<int> Llf, Lrg, Rlf, Rrg;
    unordered_set<int> w1;
    for(int i=0;i<mi;i++){ // [0,mi) is the set i want to query
        w1.insert(R[i]);
        if(s.find(R[i]) == s.end()){
            lst=Query(R[i]);
            s.insert(R[i]);
        }
    }
    vector<int> del;
    for(auto x:s){
        if(w1.find(x) == w1.end()){
            del.push_back(x);
        }
    }
    for(auto x:del){
        lst=Query(x);
        s.erase(x);
    }
    for(int i=0;i<(int)L.size()-1;i++){
        int x=L[i];
        bool hh=has(x);
        if(hh){
            Llf.push_back(x);
        } else{
            Lrg.push_back(x);
        }
    }
    
    for(int i=0;i<mi;i++){
        Rlf.push_back(R[i]);
    }
    for(int i=mi;i<(int)R.size();i++){
        Rrg.push_back(R[i]);
    }
    if(Llf.size() != Rlf.size()){
        Llf.push_back(L.back());
    } else{
        Lrg.push_back(L.back());
    }
    dnc(Llf,Rlf);
    dnc(Lrg,Rrg);
}
void Solve(int N) {
    n=N;
    for(int i=1;i<=2*n;i++){
        int q=Query(i);

        if(q==lst){
            v2.push_back(i);
        } else{
            v1.push_back(i);
        }
        lst=q;
    }
    
    
    for(auto x:v2){
        s.insert(x);
    }
    dnc(v1,v2);
    for(auto x:out){
        Answer(x.first,x.second);
    }
}

• 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