Submission #227211

#	Time	Username	Problem	Language	Result	Execution time	Memory
227211		MKopchev	Minerals (JOI19_minerals)	C++14	40 / 100	49 ms	3320 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
/*
int colour[10]={0,1,2,3,3,1,2,4,4};
int cnt[10];
bool in[10];

int Query(int pos)
{
    if(in[pos])
    {
        in[pos]=0;
        cnt[colour[pos]]--;
    }
    else
    {
        in[pos]=1;
        cnt[colour[pos]]++;
    }
    int ret=0;
    for(int i=1;i<=4;i++)ret=ret+(cnt[i]>0);

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

int current=0;

void solve(vector<int> lhs,vector<int> rhs)
{
    /*
    cout<<"LHS: ";for(auto k:lhs)cout<<k<<" ";cout<<endl;
    cout<<"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]);

    for(auto k:rhs)
    {
        int mem=Query(k);

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

        current=mem;
    }

    for(auto k:rhs)
        Query(k);

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

    current=0;

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

    solve(lhs_new[1],rhs_new[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;
    }

    for(int i=1;i<=2*n;i++)
        Query(i);

    current=0;

    solve(lhs,rhs);

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

    return 0;
}
*/

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
minerals.cpp:67: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: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10