oj.uz

Submission #167305

# Submission time Handle Problem Language Result Execution time Memory
167305 2019-12-07T09:09:00 Z ho94949 Minerals (JOI19_minerals) C++17
40 / 100
 26 ms 2960 KB 
#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 43000;

bool is_in[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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 404 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 13 ms 760 KB Output is correct
5 Correct 23 ms 1348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct
15 Incorrect 20 ms 2960 KB Wrong Answer [4]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct
15 Incorrect 20 ms 2960 KB Wrong Answer [4]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct
15 Incorrect 20 ms 2960 KB Wrong Answer [4]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct
15 Incorrect 20 ms 2960 KB Wrong Answer [4]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct
15 Incorrect 20 ms 2960 KB Wrong Answer [4]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 3 ms 404 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 23 ms 1348 KB Output is correct
10 Correct 3 ms 424 KB Output is correct
11 Correct 17 ms 1016 KB Output is correct
12 Correct 26 ms 1400 KB Output is correct
13 Correct 19 ms 1324 KB Output is correct
14 Correct 19 ms 1300 KB Output is correct
15 Incorrect 20 ms 2960 KB Wrong Answer [4]
16 Halted 0 ms 0 KB -