Submission #258669

#	Time	Username	Problem	Language	Result	Execution time	Memory
258669		Kastanda	Minerals (JOI19_minerals)	C++14	85 / 100	68 ms	3316 KiB

minerals

// M
#include<bits/stdc++.h>
#include "minerals.h"
using namespace std;
const int N = 47007 * 2;
int last = 0, M[N];
int Do(int i)
{
        M[i] ^= 1;
        int c = Query(i);
        int w = last != c;
        last = c;
        return w;
}
void Recur(vector < int > &A, vector < int > &B, int w = 3)
{
        assert(A.size() == B.size());
        if ((int)A.size() == 1)
        {
                Answer(A[0], B[0]);
                return ;
        }
        int m = (int)A.size();
        int md = max((int)(m * 0.6), 1);
        vector < int > A1, A2, B1, B2;
        for (int i = 0; i < m; i ++)
        {
                if (i < md)
                        A1.push_back(A[i]);
                else
                        A2.push_back(A[i]);
        }
        if (w == 3)
        {
                for (int i : A2)
                        assert(!Do(i));
                for (int i : B)
                {
                        if (Do(i))
                                B2.push_back(i);
                        else
                                B1.push_back(i);
                }
                Recur(A1, B1, 1);
                Recur(A2, B2, 0);
                return ;
        }
        if (w == 2)
                return void(Recur(B, A, 1));
        if (w == 1)
        {
                for (int i : A2)
                        assert(Do(i));
                for (int i : B)
                {
                        if (Do(i))
                                B2.push_back(i);
                        else
                                B1.push_back(i);
                }
                Recur(A1, B1, 3);
                Recur(A2, B2, 2);
                return ;
        }
        if (w == 0)
        {
                for (int i : A2)
                        assert(Do(i));
                for (int i : B)
                {
                        if (Do(i))
                                B1.push_back(i);
                        else
                                B2.push_back(i);
                }
                Recur(A2, B2, 3);
                Recur(A1, B1, 2);
                return ;
        }
        assert(0);
}
void Solve(int n)
{
        vector < int > A, B;
        for (int i = 1; i <= n + n; i ++)
        {
                if (Do(i))
                        A.push_back(i);
                else
                        B.push_back(i);
        }
        Recur(A, B, 3);
        return ;
}

• 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: 0 / 5
• Subtask 9: 0 / 10