Submission #167310

#	Time	Username	Problem	Language	Result	Execution time	Memory
167310		ho94949	Minerals (JOI19_minerals)	C++17	100 / 100	75 ms	4176 KiB

minerals

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

const int MAXN = 43000;

int DP[MAXN+1];
int x[MAXN+1];


bool is_in[2*MAXN];
int last = 0;
int Q(int x)
{
    is_in[x] = !is_in[x];
    return last = Query(x);
}


void recur(vector<int> A, vector<int> B)
{
    //for(auto x: A) cout << x << " "; cout << endl;
    //for(auto x: B) cout << x << " "; cout << endl;
    //cout << endl;
    assert(A.size() == B.size());
    int N = A.size();
    assert(N >= 1);
    if(N==1)
    {
        Answer(A[0], B[0]);
        return;
    }

    int M = x[N];
    
    vector<int> fA, fB, sA, sB;
    for(int i=0; i<M; ++i)
    {
        fA.push_back(A[i]);
        Q(A[i]);
    }
    bool is_fA_inside = is_in[A[0]];
    for(int i=M; i<N; ++i)
    {
        sA.push_back(A[i]);
    }
    int i = 0;
    while(fB.size() != fA.size() && sB.size() != sA.size())
    {
        int plast = last;
        Q(B[i]);
        if(is_fA_inside == (last == plast) )
            fB.push_back(B[i]);
        else
            sB.push_back(B[i]);
        ++i;
    }
    while(fB.size() != fA.size()) fB.push_back(B[i++]);
    while(sB.size() != sA.size()) sB.push_back(B[i++]);
    recur(fA, fB);
    recur(sA, sB);    
}

void init()
{
    DP[1] = 0;
    DP[2] = 2;
    x[2] = 1;
    for(int i=3; i<=MAXN; ++i)
    {
        int xa = x[i-1], xb = x[i-1]+1;
        int dpa = DP[xa] + DP[i-xa] + xa + i - 1;
        int dpb = DP[xb] + DP[i-xb] + xb + i - 1;
        if(dpa < dpb)
        {
            x[i] = xa; DP[i] = dpa;
        }
        else
        {
            x[i] = xb; DP[i] = dpb;
        }
    }
}


void Solve(int N) {
    init();
    vector<int> V, W;
    for(int i=1; i<=2*N; ++i)
    {
        int plast = last;
        Q(i);
        if(last != plast) V.push_back(i);
        else W.push_back(i);
    }
    recur(V, W);
}

• 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