oj.uz

Submission #501635

# Submission time Handle Problem Language Result Execution time Memory
501635 2022-01-04T09:00:44 Z qwerasdfzxcl Minerals (JOI19_minerals) C++14
70 / 100
 42 ms 2236 KB 
#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
mt19937_64 rng(69), rng2(74);

void Solve(int N) {
    vector<int> A, B, ans(N), on(N);

    int cur = 0;
    for (int i=1;i<=N*2;i++){
        int tmp = Query(i);
        if (tmp>cur) A.push_back(i);
        else B.push_back(i);
        cur = tmp;
    }

    shuffle(A.begin(), A.end(), rng);
    shuffle(B.begin(), B.end(), rng2);

    int cnt = 0;
    for (int i=0;i<N;i++) if (!(i&1)){
        on[i] ^= 1;
        if (on[i]) cnt++;
        else cnt--;

        cur = Query(B[i]);
    }

    //printf("YES\n");

    for (int j=0;j<16;j++){
        int cnt2 = 0;
        for (int i=0;i<N;i++){
            int tmp = Query(A[i]);
            if (tmp==cur) ans[i] |= 1<<j, cnt2++;
            cur = tmp;
            if (cnt2==cnt) break;
        }

        if (j==15) break;
        for (int i=0;i<N;i++) if (((i>>j)&1) ^ ((i>>(j+1))&1)){
            on[i] ^= 1;
            if (on[i]) cnt++;
            else cnt--;

            cur = Query(B[i]);
        }
    }

    //for (int i=0;i<N;i++) printf("%d ", ans[i]);

    for (int i=0;i<N;i++) Answer(A[i], B[ans[i]]);
}

Subtask #1
6.0 / 6.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

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 3 ms 456 KB Output is correct
4 Correct 5 ms 616 KB Output is correct
5 Correct 10 ms 904 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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct

Subtask #4
30.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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct
15 Correct 42 ms 2188 KB Output is correct
16 Correct 39 ms 2204 KB Output is correct
17 Correct 32 ms 2236 KB Output is correct
18 Correct 34 ms 2024 KB Output is correct

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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct
15 Correct 42 ms 2188 KB Output is correct
16 Correct 39 ms 2204 KB Output is correct
17 Correct 32 ms 2236 KB Output is correct
18 Correct 34 ms 2024 KB Output is correct
19 Incorrect 35 ms 2004 KB Wrong Answer [2]
20 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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct
15 Correct 42 ms 2188 KB Output is correct
16 Correct 39 ms 2204 KB Output is correct
17 Correct 32 ms 2236 KB Output is correct
18 Correct 34 ms 2024 KB Output is correct
19 Incorrect 35 ms 2004 KB Wrong Answer [2]
20 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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct
15 Correct 42 ms 2188 KB Output is correct
16 Correct 39 ms 2204 KB Output is correct
17 Correct 32 ms 2236 KB Output is correct
18 Correct 34 ms 2024 KB Output is correct
19 Incorrect 35 ms 2004 KB Wrong Answer [2]
20 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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct
15 Correct 42 ms 2188 KB Output is correct
16 Correct 39 ms 2204 KB Output is correct
17 Correct 32 ms 2236 KB Output is correct
18 Correct 34 ms 2024 KB Output is correct
19 Incorrect 35 ms 2004 KB Wrong Answer [2]
20 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 3 ms 456 KB Output is correct
8 Correct 5 ms 616 KB Output is correct
9 Correct 10 ms 904 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 11 ms 968 KB Output is correct
13 Correct 13 ms 1096 KB Output is correct
14 Correct 15 ms 916 KB Output is correct
15 Correct 42 ms 2188 KB Output is correct
16 Correct 39 ms 2204 KB Output is correct
17 Correct 32 ms 2236 KB Output is correct
18 Correct 34 ms 2024 KB Output is correct
19 Incorrect 35 ms 2004 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -