제출 #167307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167307		ho94949	Minerals (JOI19_minerals)	C++17	90 / 100	71 ms	3588 KiB

minerals

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

const int MAXN = 43000;

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 = N/2;
    
    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 Solve(int N) {
    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: 0 / 10