oj.uz

Submission #120698

# Submission time Handle Problem Language Result Execution time Memory
120698 2019-06-25T08:29:58 Z 이온조(#2959) Minerals (JOI19_minerals) C++14
85 / 100
 111 ms 3108 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 >= 10) m = (int)(N*1.0/1.618);
        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 >= 10) m = N - (int)(N*1.0/1.618);
        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 260 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 0 ms 256 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 14 ms 768 KB Output is correct
5 Correct 28 ms 1212 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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct

Subtask #4
30.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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct
15 Correct 82 ms 3000 KB Output is correct
16 Correct 89 ms 2900 KB Output is correct
17 Correct 77 ms 2872 KB Output is correct
18 Correct 77 ms 2788 KB Output is correct

Subtask #5
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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct
15 Correct 82 ms 3000 KB Output is correct
16 Correct 89 ms 2900 KB Output is correct
17 Correct 77 ms 2872 KB Output is correct
18 Correct 77 ms 2788 KB Output is correct
19 Correct 81 ms 3016 KB Output is correct
20 Correct 81 ms 2992 KB Output is correct
21 Correct 79 ms 2864 KB Output is correct
22 Correct 78 ms 2864 KB Output is correct

Subtask #6
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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct
15 Correct 82 ms 3000 KB Output is correct
16 Correct 89 ms 2900 KB Output is correct
17 Correct 77 ms 2872 KB Output is correct
18 Correct 77 ms 2788 KB Output is correct
19 Correct 81 ms 3016 KB Output is correct
20 Correct 81 ms 2992 KB Output is correct
21 Correct 79 ms 2864 KB Output is correct
22 Correct 78 ms 2864 KB Output is correct
23 Correct 85 ms 2984 KB Output is correct
24 Correct 88 ms 2980 KB Output is correct
25 Correct 92 ms 3108 KB Output is correct
26 Correct 85 ms 2968 KB Output is correct

Subtask #7
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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct
15 Correct 82 ms 3000 KB Output is correct
16 Correct 89 ms 2900 KB Output is correct
17 Correct 77 ms 2872 KB Output is correct
18 Correct 77 ms 2788 KB Output is correct
19 Correct 81 ms 3016 KB Output is correct
20 Correct 81 ms 2992 KB Output is correct
21 Correct 79 ms 2864 KB Output is correct
22 Correct 78 ms 2864 KB Output is correct
23 Correct 85 ms 2984 KB Output is correct
24 Correct 88 ms 2980 KB Output is correct
25 Correct 92 ms 3108 KB Output is correct
26 Correct 85 ms 2968 KB Output is correct
27 Correct 87 ms 3104 KB Output is correct
28 Correct 92 ms 2988 KB Output is correct
29 Correct 91 ms 3028 KB Output is correct
30 Correct 89 ms 2844 KB Output is correct

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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct
15 Correct 82 ms 3000 KB Output is correct
16 Correct 89 ms 2900 KB Output is correct
17 Correct 77 ms 2872 KB Output is correct
18 Correct 77 ms 2788 KB Output is correct
19 Correct 81 ms 3016 KB Output is correct
20 Correct 81 ms 2992 KB Output is correct
21 Correct 79 ms 2864 KB Output is correct
22 Correct 78 ms 2864 KB Output is correct
23 Correct 85 ms 2984 KB Output is correct
24 Correct 88 ms 2980 KB Output is correct
25 Correct 92 ms 3108 KB Output is correct
26 Correct 85 ms 2968 KB Output is correct
27 Correct 87 ms 3104 KB Output is correct
28 Correct 92 ms 2988 KB Output is correct
29 Correct 91 ms 3028 KB Output is correct
30 Correct 89 ms 2844 KB Output is correct
31 Incorrect 111 ms 3104 KB Wrong Answer [2]
32 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 260 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 28 ms 1212 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 19 ms 1072 KB Output is correct
12 Correct 29 ms 1408 KB Output is correct
13 Correct 29 ms 1288 KB Output is correct
14 Correct 46 ms 1288 KB Output is correct
15 Correct 82 ms 3000 KB Output is correct
16 Correct 89 ms 2900 KB Output is correct
17 Correct 77 ms 2872 KB Output is correct
18 Correct 77 ms 2788 KB Output is correct
19 Correct 81 ms 3016 KB Output is correct
20 Correct 81 ms 2992 KB Output is correct
21 Correct 79 ms 2864 KB Output is correct
22 Correct 78 ms 2864 KB Output is correct
23 Correct 85 ms 2984 KB Output is correct
24 Correct 88 ms 2980 KB Output is correct
25 Correct 92 ms 3108 KB Output is correct
26 Correct 85 ms 2968 KB Output is correct
27 Correct 87 ms 3104 KB Output is correct
28 Correct 92 ms 2988 KB Output is correct
29 Correct 91 ms 3028 KB Output is correct
30 Correct 89 ms 2844 KB Output is correct
31 Incorrect 111 ms 3104 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -