oj.uz

Submission #611197

# Submission time Handle Problem Language Result Execution time Memory
611197 2022-07-29T04:09:16 Z alireza_kaviani Minerals (JOI19_minerals) C++17
40 / 100
 45 ms 7688 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 = 16;

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

int query(int ind , int x){
  cnt -= mark[x];
  mark[x] ^= 1;
  cnt += mark[x];
  int res = Query(x);
  if(ind % 2 == 0){
    return res;
  }
  return n + res - cnt;
}

void Solve(int N) {
  n = N;
  for(int i = 1 ; i <= 2 * n ; i++){
    int x = query(0 , i);
    if(x == SZ(v1)){
      v2.push_back(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 = 0 ; j < n ; j++){
      Q[j].clear();
    }
    for(int j = 0 ; j < n ; j++){
      M[j] = max(0 , (R[j] + L[j]) / 2);
      Q[M[j]].push_back(j);
    }
    for(int j = 0 ; j < n ; j++){
      int x = query(i + 1 , v1[j]);
      for(int k : Q[j]){
        int y = query(i + 1 , v2[k]);
        if(x != y){
          L[k] = M[k];
        }
        else{
          R[k] = M[k];
        }
        x = y;
      }
    }
  }
  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 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
4 Correct 10 ms 3664 KB Output is correct
5 Correct 20 ms 4576 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct
15 Incorrect 45 ms 7688 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 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct
15 Incorrect 45 ms 7688 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 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct
15 Incorrect 45 ms 7688 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 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct
15 Incorrect 45 ms 7688 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 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct
15 Incorrect 45 ms 7688 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 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 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 5 ms 3128 KB Output is correct
8 Correct 10 ms 3664 KB Output is correct
9 Correct 20 ms 4576 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 17 ms 4168 KB Output is correct
12 Correct 20 ms 4680 KB Output is correct
13 Correct 16 ms 4712 KB Output is correct
14 Correct 18 ms 4560 KB Output is correct
15 Incorrect 45 ms 7688 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -