Submission #485995

#	Time	Username	Problem	Language	Result	Execution time	Memory
485995		blue	Minerals (JOI19_minerals)	C++17	40 / 100	28 ms	3480 KiB

minerals

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

using vi = vector<int>;

const int maxN = 43'000;

int N;

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

void dnc(vi L, vi R, bool b)
{
    // 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
    {
        int K = int(L.size());

        vi L1, L2;
        for(int i = 0; i < K/2; i++)
            L1.push_back(L[i]);

        for(int i = K/2; i < K; i++)
            L2.push_back(L[i]);

        int Q;

        // for(int l: L1)
        //     Q = Query(l); //enable

        if(b)
        {
            for(int l: L2)
                Q = Query(l);
        }
        else
        {
            for(int l: L1)
                Q = Query(l);
        }

        vi R1, R2;

        for(int r:R)
        {
            int Q1 = Query(r);
            if(Q1 == Q)
            {
                R1.push_back(r);
            }
            else
            {
                R2.push_back(r);
            }
            Q1 = Query(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++)
    {
        int Q = Query(i);
        if(Q > ct)
        {
            // cerr << "increasing ct = " << ct << " at " << i << '\n';
            ct++;
            mushroom[i] = ct;
            // cerr << i << " : " << mushroom[i] << '\n';
        }
    }
    for(int i = 1; i <= 2*N; i++)
        if(!mushroom[i])
            Query(i);

    // cerr << "check\n";

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


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



    dnc(leftval, rightval, 1);
}

Compilation message (stderr)

minerals.cpp: In function 'void dnc(vi, vi, bool)':
minerals.cpp:56:13: warning: 'Q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |             if(Q1 == Q)
      |             ^~

• 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