Submission #227269

#	Time	Username	Problem	Language	Result	Execution time	Memory
227269		MKopchev	Minerals (JOI19_minerals)	C++14	100 / 100	109 ms	11940 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;
}
*/
mt19937 rng(42);

vector< pair<int,int> > outp;

int current=0;

int which_is_active(int le,int ri)
{
    if(le)return 0;
    return 1;
}

const int MX=1000;

int opt[MX]={0,0,1,1,1,1,1,3,3,1};

double exp_time[MX][MX];

double dp_time[MX];

double coeff=/*(1+sqrt(5))/2+1*/2.6246;

void solve(vector<int> lhs,vector<int> rhs,bool active_lhs)
{
    shuffle(rhs.begin(),rhs.end(),rng);

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

    int mid=lhs.size()/2;

    if(lhs.size()<MX)mid=opt[lhs.size()];

    else mid=lhs.size()/coeff;

    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)
{
    for(int r=1;r<MX;r++)
        for(int b=1;b<MX;b++)
        {
            exp_time[r][b]=1+exp_time[r-1][b]*r/(r+b)+exp_time[r][b-1]*b/(r+b);
        }

    for(int n_now=2;n_now<MX;n_now++)
    {
        dp_time[n_now]=1e9;
        for(int mid=1;mid<n_now;mid++)
        {
            double now=dp_time[mid]+dp_time[n_now-mid]+mid+exp_time[mid][n_now-mid];

            if(dp_time[n_now]>now)
            {
                opt[n_now]=mid;
                dp_time[n_now]=now;
            }
        }
    }

    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;

    shuffle(colour+1,colour+2*n+1,rng);
}

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:95: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: 10 / 10