Submission #233668

#	Time	Username	Problem	Language	Result	Execution time	Memory
233668		AlexLuchianov	Minerals (JOI19_minerals)	C++14	40 / 100	85 ms	5108 KiB

minerals

#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 (stderr)

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 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10