Submission #227256

#	Time	Username	Problem	Language	Result	Execution time	Memory
227256		MKopchev	Minerals (JOI19_minerals)	C++14	90 / 100	68 ms	3716 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

int used=0;

int colour[nmax]={0,1,2,3,3,1,2,4,4};
int cnt[nmax];
bool in[nmax];

int CURRENT;
/*
int Query(int pos)
{
    used++;

    CURRENT=CURRENT-(cnt[colour[pos]]>0);

    if(in[pos])
    {
        in[pos]=0;
        cnt[colour[pos]]--;
    }
    else
    {
        in[pos]=1;
        cnt[colour[pos]]++;
    }

    CURRENT=CURRENT+(cnt[colour[pos]]>0);

    return CURRENT;
}
void Answer(int a,int b)
{
    return;
    cout<<a<<" "<<b<<endl;
}
*/
vector< pair<int,int> > outp;

int current=0;

int which_is_active(int le,int ri)
{
    if(le)return 0;
    return 1;
}
void solve(vector<int> lhs,vector<int> rhs,bool active_lhs)
{
    /*
    cout<<active_lhs<<" LHS: ";for(auto k:lhs)cout<<k<<" ";cout<<endl;
    cout<<active_rhs<<" RHS: ";for(auto k:rhs)cout<<k<<" ";cout<<endl;
    cout<<"---"<<endl;
    */

    if(lhs.size()==1)
    {
        outp.push_back({lhs[0],rhs[0]});
        return;
    }

    int mid=lhs.size()/2;

    vector<int> lhs_new[2],rhs_new[2];

    lhs_new[0]={};lhs_new[1]={};

    rhs_new[0]={};rhs_new[1]={};

    for(int i=0;i<mid;i++)
    {
        int mem=Query(lhs[i]);

        current=mem;

        lhs_new[0].push_back(lhs[i]);
    }

    for(int i=mid;i<lhs.size();i++)
        lhs_new[1].push_back(lhs[i]);

    bool type_lhs[2]={!active_lhs,active_lhs};

    for(auto k:rhs)
    {
        if(rhs_new[0].size()==lhs_new[0].size())rhs_new[1].push_back(k);
        else if(rhs_new[1].size()==lhs_new[1].size())rhs_new[0].push_back(k);
        else
        {
            int mem=Query(k);

            if(current==mem)rhs_new[which_is_active(type_lhs[0],type_lhs[1])].push_back(k);
            else rhs_new[!which_is_active(type_lhs[0],type_lhs[1])].push_back(k);

            current=mem;
        }
    }

    solve(lhs_new[0],rhs_new[0],type_lhs[0]);

    solve(lhs_new[1],rhs_new[1],type_lhs[1]);
}
void Solve(int n)
{
    vector<int> lhs={},rhs={};

    for(int i=1;i<=2*n;i++)
    {
        int mem=Query(i);
        if(current<mem)lhs.push_back(i);
        else rhs.push_back(i);

        current=mem;
    }

    solve(lhs,rhs,1);

    for(int i=0;i<n;i++)
        Answer(outp[i].first,outp[i].second);
}
/*
int n;
void create()
{

    for(int i=1;i<=n;i++)
        colour[i]=i;
    for(int i=n+1;i<=2*n;i++)
        colour[i]=i-n;

}

int main()
{
    n=4.3e4;

    create();

    Solve(n);

    cout<<"used= "<<used<<endl;

    return 0;
}
*/

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=mid;i<lhs.size();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