oj.uz

답안 #233670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233670 2020-05-21T10:20:20 Z AlexLuchianov Minerals (JOI19_minerals) C++14
40 / 100
 80 ms 5160 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 < 100; 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

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 8 ms 1536 KB Output is correct
3 Correct 12 ms 1792 KB Output is correct
4 Correct 20 ms 2216 KB Output is correct
5 Correct 39 ms 3000 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct
15 Incorrect 80 ms 5160 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct
15 Incorrect 80 ms 5160 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct
15 Incorrect 80 ms 5160 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct
15 Incorrect 80 ms 5160 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct
15 Incorrect 80 ms 5160 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 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 5 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 20 ms 2216 KB Output is correct
9 Correct 39 ms 3000 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 25 ms 2432 KB Output is correct
12 Correct 40 ms 2936 KB Output is correct
13 Correct 38 ms 2936 KB Output is correct
14 Correct 36 ms 2936 KB Output is correct
15 Incorrect 80 ms 5160 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -