oj.uz

Submission #611195

# Submission time Handle Problem Language Result Execution time Memory
611195 2022-07-29T04:08:37 Z alireza_kaviani Minerals (JOI19_minerals) C++17
40 / 100
 39 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 = 17;

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 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
3 Correct 7 ms 3152 KB Output is correct
4 Correct 12 ms 3600 KB Output is correct
5 Correct 24 ms 4608 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct
15 Incorrect 39 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 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct
15 Incorrect 39 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 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct
15 Incorrect 39 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 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct
15 Incorrect 39 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 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct
15 Incorrect 39 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 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 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 5 ms 2888 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 12 ms 3600 KB Output is correct
9 Correct 24 ms 4608 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 15 ms 4148 KB Output is correct
12 Correct 21 ms 4616 KB Output is correct
13 Correct 15 ms 4612 KB Output is correct
14 Correct 15 ms 4636 KB Output is correct
15 Incorrect 39 ms 7688 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -