oj.uz

Submission #258666

# Submission time Handle Problem Language Result Execution time Memory
258666 2020-08-06T10:53:26 Z Kastanda Minerals (JOI19_minerals) C++14
40 / 100
 76 ms 3264 KB 
// 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.4), 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 : A1)
                        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 ;
        }
        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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 20 ms 1488 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct
15 Incorrect 76 ms 3264 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct
15 Incorrect 76 ms 3264 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct
15 Incorrect 76 ms 3264 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct
15 Incorrect 76 ms 3264 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct
15 Incorrect 76 ms 3264 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 20 ms 1488 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 13 ms 1152 KB Output is correct
12 Correct 22 ms 1496 KB Output is correct
13 Correct 20 ms 1508 KB Output is correct
14 Correct 18 ms 1464 KB Output is correct
15 Incorrect 76 ms 3264 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -