Submission #486184

#	Time	Username	Problem	Language	Result	Execution time	Memory
486184		blue	Minerals (JOI19_minerals)	C++17	100 / 100	72 ms	4180 KiB

minerals

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

using vi = vector<int>;

const int maxN = 43'000;

int N;

vi mineral(1+2*maxN, 0);

int last_ans = 0;

int sz(vi& x)
{
    return int(x.size());
}

random_device rd;
mt19937 g(rd());

void dnc(vi L, vi R, bool bL)
{
    // cerr << "dnc " << b << " : ";
    // for(int l:L) cerr << l << ' ';
    // cerr << " | ";
    // for(int r:R) cerr << r << ' ';
    // cerr << "\n";
    if(int(L.size()) == 1)
        Answer(L[0], R[0]);
    else if(int(L.size()) == 2)
    {
        if(!bL) last_ans = Query(L[0]);
        else last_ans = Query(L[1]); //0 is active

        int prev_ans = last_ans;
        last_ans = Query(R[0]);
        if(prev_ans == last_ans)
        {
            Answer(L[0], R[0]);
            Answer(L[1], R[1]);
        }
        else
        {
            Answer(L[0], R[1]);
            Answer(L[1], R[0]);
        }
    }
    else
    {
        int K = int(L.size());
        shuffle(L.begin(), L.end(), g);

        double r = 0.6;

        vi L1, L2;

        if(bL)
        {
            for(int i = 0; i < int(K*r); i++)
                L1.push_back(L[i]);

            for(int i = int(K*r); i < K; i++)
                L2.push_back(L[i]);
        }
        else
        {
            for(int i = 0; i < int(K*(1.0-r)); i++)
                L1.push_back(L[i]);

            for(int i = int(K*(1.0-r)); i < K; i++)
                L2.push_back(L[i]);
        }






        if(bL)
        {
            for(int l: L2)
                last_ans = Query(l);
        }
        else
        {
            for(int l: L1)
                last_ans = Query(l);
        }

        vi R1, R2;
        shuffle(R.begin(), R.end(), g);

        for(int r:R)
        {
            if(sz(R1) == sz(L1))
            {
                R2.push_back(r);
            }
            else if(sz(R2) == sz(L2))
            {
                R1.push_back(r);
            }
            else
            {
                int prev_ans = last_ans;
                last_ans = Query(r);
                if(last_ans == prev_ans)
                {
                    R1.push_back(r);
                }
                else
                {
                    R2.push_back(r);
                }
            }
        }

        dnc(L1, R1, 1);
        dnc(L2, R2, 0);
    }
}

void Solve(int N_)
{
    N = N_;

    int ct = 0;

    for(int i = 1; i <= 2*N; i++)
    {
        last_ans = Query(i);
        if(last_ans > ct)
        {
            // cerr << "increasing ct = " << ct << " at " << i << '\n';
            ct++;
            mineral[i] = ct;
            // cerr << i << " : " << mineral[i] << '\n';
        }
    }

    // cerr << "check\n";

    // for(int i = 1; i <= 2*N; i++) cerr << i << " : " << mineral[i] << '\n';


    vi leftval, rightval;
    for(int i = 1; i <= 2*N; i++)
    {
        if(mineral[i])
            leftval.push_back(i);
        else
            rightval.push_back(i);
    }

    dnc(leftval, rightval, 1);
}

• 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