Submission #815768

#	Time	Username	Problem	Language	Result	Execution time	Memory
815768		JakobZorz	Minerals (JOI19_minerals)	C++14	40 / 100	30 ms	3404 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>m){
    //cout<<m.size()<<"\n";
    if(m.size()==2){
        Answer(m[0],m[1]);
        return;
    }
    
    int n=(int)m.size()/2;
    for(int i:m){
        if(query(i)>n/2)
            query(i);
        if(last*2==inside)
            break;
    }
    
    vector<int>m1,m2;
    
    for(int i:m){
        if(flag[i])
            m1.push_back(i);
        else
            m2.push_back(i);
    }
    
    
    bool removing=true;
    for(int i:m)
        if(flag[i])
            if(query(i)<=(int)m1.size()/4)
                break;
    
    solve(m1);
    solve(m2);
}

void Solve(int N){
    vector<int>m;
    for(int i=1;i<=2*N;i++)
        m.push_back(i);
    srand((int)time(0));
    for(int i=0;i<2*N;i++)
        swap(m[i],m[rand()%(2*N)]);
    solve(m);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>)':
minerals.cpp:45:10: warning: unused variable 'removing' [-Wunused-variable]
   45 |     bool removing=true;
      |          ^~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10