Submission #487285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
487285	2021-11-15T03:35:47 Z	Rainbowbunny	Minerals (JOI19_minerals)	C++17	40 / 100	32 ms	2336 KB

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 <= 15; 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.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	200 KB	Output is correct
2	Correct	200 KB	Output is correct
3	Correct	200 KB	Output is correct
4	Correct	200 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	328 KB	Output is correct
2	Correct	2 ms	328 KB	Output is correct
3	Correct	4 ms	488 KB	Output is correct
4	Correct	8 ms	712 KB	Output is correct
5	Correct	12 ms	1056 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct
15	Incorrect	32 ms	2336 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct
15	Incorrect	32 ms	2336 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct
15	Incorrect	32 ms	2336 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct
15	Incorrect	32 ms	2336 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct
15	Incorrect	32 ms	2336 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	4 ms	488 KB	Output is correct
8	Correct	8 ms	712 KB	Output is correct
9	Correct	12 ms	1056 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	8 ms	840 KB	Output is correct
12	Correct	14 ms	1064 KB	Output is correct
13	Correct	11 ms	1096 KB	Output is correct
14	Correct	12 ms	1116 KB	Output is correct
15	Incorrect	32 ms	2336 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-

Submission #487285

Compilation message