oj.uz

Submission #120694

# Submission time Handle Problem Language Result Execution time Memory
120694 2019-06-25T08:27:50 Z 이온조(#2959) Minerals (JOI19_minerals) C++14
40 / 100
 82 ms 3128 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

bool chk[100009];

int query(int x) {
    chk[x] = !chk[x];
    //printf("query x: %d\n", x);
    return Query(x);
}

void answer(int a, int b) {
    //printf("answer: (%d, %d)\n", a, b);
    Answer(a, b);
}

pair<vi, vi> split(int N) {
    vector<int> A, B, S;
    for(int i=1; i<=2*N; i++) S.push_back(i);
    random_shuffle(S.begin(), S.end());
    int pr = 0, i = 0;
    for(i=0; i<2*N; i++) {
        int it = S[i];
        int Q = query(it);
        if(pr != Q) A.push_back(it);
        else B.push_back(it);
        if((int)A.size() == N || (int)B.size() == N) break;
        pr = Q;
    }
    if((int)A.size() == N) for(++i; i<2*N; i++) B.push_back(S[i]);
    else for(++i; i<2*N; i++) A.push_back(S[i]);
    return {A, B};
}

void go(vector<int> &A, vector<int> &B, bool AC) {
    //puts("AB");
    //for(auto& it: A) printf("%d ",it); puts("");
    //for(auto& it: B) printf("%d ",it); puts("");
    random_shuffle(A.begin(), A.end());
    random_shuffle(B.begin(), B.end());
    int N = A.size();
    if(N == 1) {
        answer(A[0], B[0]);
        return;
    }
    if(!AC) {
        int m = N/2, pr;
        if(N >= 4) m = N*2/3;
        vector<int> LA, RA, LB, RB;
        for(int i=0; i<m; i++) {
            pr = query(A[i]);
            LA.push_back(A[i]);
        }
        for(int i=m; i<N; i++) RA.push_back(A[i]);
        int i;
        for(i=0; i<N; i++) {
            int Q = query(B[i]);
            if(pr != Q) RB.push_back(B[i]);
            else LB.push_back(B[i]);
            if(RB.size() == RA.size()) break;
            if(LB.size() == LA.size()) break;
            pr = Q;
        }
        if(RB.size() == RA.size()) for(++i; i<N; i++) LB.push_back(B[i]);
        else for(++i; i<N; i++) RB.push_back(B[i]);
        go(LA, LB, 1);
        go(RA, RB, 0);
    }
    if(AC) {
        int m = N/2, pr;
        if(N >= 4) m = N*2/3;
        vector<int> LA, RA, LB, RB;
        for(int i=0; i<m; i++) {
            pr = query(A[i]);
            LA.push_back(A[i]);
        }
        for(int i=m; i<N; i++) RA.push_back(A[i]);
        int i;
        for(i=0; i<N; i++) {
            int Q = query(B[i]);
            if(pr != Q) LB.push_back(B[i]);
            else RB.push_back(B[i]);
            if(RB.size() == RA.size()) break;
            if(LB.size() == LA.size()) break;
            pr = Q;
        }
        if(RB.size() == RA.size()) for(++i; i<N; i++) LB.push_back(B[i]);
        else for(++i; i<N; i++) RB.push_back(B[i]);
        go(LA, LB, 0);
        go(RA, RB, 1);
    }
}

void Solve(int N) {
    vi A, B; tie(A, B) = split(N);
    go(A, B, 1);
}

Compilation message

minerals.cpp: In function 'void go(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:83:13: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(pr != Q) LB.push_back(B[i]);
             ^~
minerals.cpp:60:13: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(pr != Q) RB.push_back(B[i]);
             ^~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 16 ms 896 KB Output is correct
5 Correct 30 ms 1408 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct
15 Incorrect 82 ms 3128 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct
15 Incorrect 82 ms 3128 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct
15 Incorrect 82 ms 3128 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct
15 Incorrect 82 ms 3128 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct
15 Incorrect 82 ms 3128 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 30 ms 1408 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 20 ms 1056 KB Output is correct
12 Correct 29 ms 1348 KB Output is correct
13 Correct 29 ms 1416 KB Output is correct
14 Correct 31 ms 1288 KB Output is correct
15 Incorrect 82 ms 3128 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -