Submission #487286

#	Time	Username	Problem	Language	Result	Execution time	Memory
487286		Rainbowbunny	Minerals (JOI19_minerals)	C++17	75 / 100	38 ms	2388 KiB

minerals

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

const int MAXN = 45005;

int lst = 0;
bool In[2 * MAXN];
vector <int> A, B;

void Solve(int n)
{
    for(int i = 1; i <= 2 * n; i++)
    {
        int cur = Query(i);
        In[i] ^= 1;
        if(cur == lst)
        {
            B.push_back(i);
        }
        else
        {
            A.push_back(i);
        }
        lst = cur;
    }
    vector <pair <int, int> > BFS;
    BFS.emplace_back(0, n - 1);
    for(int times = 1; times <= 16; times++)
    {
        vector <pair <int, int> > NextLayer;
        // for(auto x : B)
        // {
        //     cout << x << ' ';
        // }
        // cout << '\n';
        for(auto x : BFS)
        {
            int mid = (x.first + x.second) >> 1;
            // cout << x.first << ' ' << mid << ' ' << mid + 1 << ' ' << x.second << '\n';

            if(x.first < x.second)
            {
                NextLayer.emplace_back(x.first, mid);
                NextLayer.emplace_back(mid + 1, x.second);
                // for(int i = 1; i <= 2 * n; i++)
                // {
                //     cout << In[i] << ' ';
                // }
                // cout << '\n';
                if(In[A[mid + 1]])
                {
                    for(int i = mid + 1; i <= x.second; i++)
                    {
                        assert(In[A[i]]);
                        lst = Query(A[i]);
                        In[A[i]] ^= 1;
                    }
                }
                // cout << "owo" << endl;
                if(!In[A[x.first]])
                {
                    for(int i = x.first; i <= mid; i++)
                    {
                        assert(!In[A[i]]);
                        lst = Query(A[i]);
                        In[A[i]] ^= 1;
                    }
                }
                // for(int i = 1; i <= 2 * n; i++)
                // {
                //     cout << In[i] << ' ';
                // }
                // cout << '\n';
                vector <int> L, R;
                if(In[B[x.first]])
                {
                    for(int i = x.first; i <= x.second; i++)
                    {
                        assert(In[B[i]]);
                        int tmp = Query(B[i]);
                        In[B[i]] ^= 1;
                        if(tmp == lst)
                        {
                            L.push_back(B[i]);
                        }
                        else
                        {
                            R.push_back(B[i]);
                        }
                        lst = tmp;
                    }
                }
                else
                {
                    for(int i = x.first; i <= x.second; i++)
                    {
                        assert(!In[B[i]]);
                        int tmp = Query(B[i]);
                        In[B[i]] ^= 1;
                        if(tmp == lst)
                        {
                            L.push_back(B[i]);
                        }
                        else
                        {
                            R.push_back(B[i]);
                        }
                        lst = tmp;
                    }
                }
                // cout << L.size() << ' ' << R.size() << '\n';
                for(int i = x.first; i <= mid; i++)
                {
                    B[i] = L[i - x.first];
                }
                for(int i = mid + 1; i <= x.second; i++)
                {
                    B[i] = R[i - mid - 1];
                }
            }
            else
            {
                if(In[A[x.first]])
                {
                    Query(A[x.first]);
                    In[A[x.first]] ^= 1;
                }
            }
        }
        BFS.swap(NextLayer);
    }
    for(int i = 0; i < n; i++)
    {
        Answer(A[i], B[i]);
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10