oj.uz

Submission #233668

# Submission time Handle Problem Language Result Execution time Memory
233668 2020-05-21T10:19:18 Z AlexLuchianov Minerals (JOI19_minerals) C++14
40 / 100
 85 ms 5108 KB 
#include "minerals.h"
#include <vector>
#include <random>
#include <algorithm>

using namespace std;

int const nmax = 43000;
int ord[1 + 2 * nmax];
vector<int> basic, spec;
int start[1 + nmax], stop[1 + nmax], sol[1 + nmax];
int active[1 + 2 * nmax];

vector<int> g[1 + nmax];

int last = 0;

int query(int pos){
  int curr = Query(pos);
  if(last == curr)
    return 0;
  else {
    last = curr;
    return 1;
  }
}

void prune(int n, int step){
  for(int i = 0; i < n; i++)
    g[i].clear();
  bool flag = 0;

  for(int i = 0; i < n; i++)
    if(start[i] < stop[i]){
      int mid = (stop[i] + start[i]) / 2;
      g[mid].push_back(i);
      flag = 1;
    }

  if(flag == 0)
    return ;

  if(step % 2 == 0){
    for(int i = n - 1; 0 <= i; i--){
      for(int h = 0; h < g[i].size(); h++){
        int to = g[i][h];
        if(query(spec[to]) == 1)
          sol[to] = 0;
        else
          sol[to] = 1;
      }
      query(basic[i]);
    }
  } else {
    for(int i = 0; i < n; i++){
      query(basic[i]);
      for(int h = 0; h < g[i].size(); h++){
        int to = g[i][h];
        if(query(spec[to]) == 1)
          sol[to] = 0;
        else
          sol[to] = 1;
      }
    }
  }

  for(int i = 0; i < n; i++)
    if(start[i] < stop[i]){
      int mid = (start[i] + stop[i]) / 2;
      if(sol[i] == 1)
        stop[i] = mid;
      else
        start[i] = mid + 1;
    }
}

void Solve(int n) {
  for(int i = 1; i <= 2 * n; i++)
    ord[i] = i;
  random_shuffle(ord + 1, ord + 2 * n + 1);
  int last = 0;
  for(int i = 1; i <= 2 * n; i++){
    if(query(ord[i]) == 1) {
      active[ord[i]] = 1;
      basic.push_back(ord[i]);
    } else{
      ++last;
      spec.push_back(ord[i]);
      start[spec.size() - 1] = 0 ;
      stop[spec.size() - 1] = basic.size() - 1;
    }
  }

  for(int i = 0; i < 20; i++)
    prune(n, i);
  for(int i = 0; i < spec.size(); i++)
    Answer(spec[i], basic[start[i]]);
}

Compilation message

minerals.cpp: In function 'void prune(int, int)':
minerals.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[i].size(); h++){
                      ~~^~~~~~~~~~~~~
minerals.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[i].size(); h++){
                      ~~^~~~~~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < spec.size(); i++)
                  ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1536 KB Output is correct
2 Correct 7 ms 1536 KB Output is correct
3 Correct 11 ms 1792 KB Output is correct
4 Correct 17 ms 2212 KB Output is correct
5 Correct 34 ms 2936 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct
15 Incorrect 85 ms 5108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct
15 Incorrect 85 ms 5108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct
15 Incorrect 85 ms 5108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct
15 Incorrect 85 ms 5108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct
15 Incorrect 85 ms 5108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 17 ms 2212 KB Output is correct
9 Correct 34 ms 2936 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 23 ms 2432 KB Output is correct
12 Correct 32 ms 2936 KB Output is correct
13 Correct 31 ms 2936 KB Output is correct
14 Correct 35 ms 2936 KB Output is correct
15 Incorrect 85 ms 5108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -