Submission #815780

#	Time	Username	Problem	Language	Result	Execution time	Memory
815780		JakobZorz	Minerals (JOI19_minerals)	C++14	100 / 100	50 ms	4980 KiB

minerals

#include"minerals.h"
#include<iostream>
#include<vector>
using namespace std;

int inside;
int last;
int flag[100000];
int query(int a){
    flag[a]++;
    flag[a]%=2;
    if(flag[a])
        inside++;
    else
        inside--;
    last=Query(a);
    return last;
}

void solve(vector<int>up,vector<int>dn,bool inv){
    //cout<<up.size()<<" "<<dn.size()<<"\n";
    
    if(up.size()==1){
        Answer(up[0],dn[0]);
        return;
    }
    
    vector<int>up1,up2;
    vector<int>dn1,dn2;
    int mid;
    if(inv){
        mid=(int)(up.size()*2)/3;
    }else
        mid=(int)(up.size()+2)/3;
    
    for(int i=0;i<mid;i++)
        up1.push_back(up[i]);
    for(int i=mid;i<(int)up.size();i++)
        up2.push_back(up[i]);
    
    if(inv)
        for(int i:up2)
            query(i);
    else
        for(int i:up1)
            query(i);
    
    for(int i:dn){
        if(dn1.size()==up1.size()){
            dn2.push_back(i);
            continue;
        }
        
        if(dn2.size()==up2.size()){
            dn1.push_back(i);
            continue;
        }
        
        int prev=last;
        query(i);
        bool to_first=prev==last;
        
        if(to_first)
            dn1.push_back(i);
        else
            dn2.push_back(i);
    }
    
    solve(up1,dn1,true);
    solve(up2,dn2,false);
}

void Solve(int N){
    vector<int>elements;
    for(int i=1;i<=2*N;i++)
        elements.push_back(i);
    for(int i=0;i<2*N;i++)
        swap(elements[i],elements[rand()%(2*N)]);
    
    vector<int>up,dn;
    int prev=0;
    for(int i:elements){
        query(i);
        if(last!=prev)
            up.push_back(i);
        else
            dn.push_back(i);
        prev=last;
    }
    
    solve(up,dn,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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10