oj.uz

Submission #611142

# Submission time Handle Problem Language Result Execution time Memory
611142 2022-07-29T03:50:42 Z alireza_kaviani Minerals (JOI19_minerals) C++17
40 / 100
 24 ms 5452 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

#define SZ(x) int((x).size())

const int MAXN = 1e5 + 10;
const int LOG = 17;

int L[MAXN] , M[MAXN] , R[MAXN];
vector<int> v1 , v2 , Q[MAXN];

void Solve(int n) {
  for(int i = 1 ; i <= 2 * n ; i++){
    int x = Query(i);
    if(x == SZ(v1)){
      v2.push_back(i);
      Query(i);
    }
    else{
      v1.push_back(i);
    }
  }

  for(int i = 0 ; i < n ; i++){
    L[i] = -1; R[i] = n - 1;
  }

  for(int i = 0 ; i < LOG ; i++){
    for(int j : v1){
      Query(j);
    }
    for(int j = 0 ; j < n ; j++){
      Q[j].clear();
    }
    for(int j = 0 ; j < n ; j++){
      if(R[j] - L[j] <= 1)  continue;
      M[j] = (R[j] + L[j]) / 2;
      Q[M[j]].push_back(j);
    }
    for(int j = 0 ; j < n ; j++){
      int x = Query(v1[j]);
      for(int k : Q[j]){
        int y = Query(v2[k]);
        if(x != y){
          L[k] = M[k];
        }
        else{
          R[k] = M[k];
        }
        Query(v2[k]);
      }
    }
  }
  for(int i = 0 ; i < n ; i++){
    Answer(v2[i] , v1[R[i]]);
  }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2768 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 6 ms 3024 KB Output is correct
4 Correct 13 ms 3548 KB Output is correct
5 Correct 24 ms 4480 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct
15 Incorrect 23 ms 5452 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 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct
15 Incorrect 23 ms 5452 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 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct
15 Incorrect 23 ms 5452 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 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct
15 Incorrect 23 ms 5452 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 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct
15 Incorrect 23 ms 5452 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 2656 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 3 ms 2768 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 6 ms 3024 KB Output is correct
8 Correct 13 ms 3548 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 18 ms 4172 KB Output is correct
12 Correct 22 ms 4560 KB Output is correct
13 Correct 17 ms 4552 KB Output is correct
14 Correct 19 ms 4560 KB Output is correct
15 Incorrect 23 ms 5452 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -