Submission #631712

#	Time	Username	Problem	Language	Result	Execution time	Memory
631712		cadmiumsky	Minerals (JOI19_minerals)	C++14	75 / 100	38 ms	3532 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;

int getbit(int x, int shift) {
  if(shift < 0) return 1;
  return (x & (1 << shift)) > 0;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(69);

int rnd(int x) { return rng() % x; }

namespace Q {
  int last = 0, curr = 0;
  bool isdiff() {return last != curr; }
  bool query(int x) { last = curr; curr = Query(x); return isdiff(); }
}
using namespace Q;
const int nmax = 43e3 + 5;
int lg[nmax];
void metasolve(vector<int> in, vector<int> out, vector<int> offset, vector<int> lim) {
  int N = in.size();
  for(int i = 0; i <= lg[N]; i++) {
    for(int j = 0; j < N; j++) {
      if(getbit(j, i) ^ getbit(j, i - 1))
	query(in[j]);
    }
    for(int j = 0; j < N; j++) {
      if(offset[j] + (1 << i) >= lim[j])
	continue;
      if(!query(out[j]))	
	offset[j] += (1 << i);
    }
  }
  for(int i = 0; i < offset.size(); i++) {
    Answer(in[offset[i]], out[i]);
  }
}

void Solve(int N) {
  lg[0] = -1;
  for(int i = 1; i <= N; i++)
    lg[i] = lg[i >> 1] + 1;
  vector<int> in, out;
  vector<int> offset, lim;
  vector<int> order(2 * N);
  iota(all(order), 1);
  random_shuffle(all(order), rnd);
  
  int last = 0, l = 0;
  for(auto x : order) {
    if(query(x))
      in.push_back(x);
    else {
      out.push_back(x);
      lim.push_back(in.size());
      offset.push_back(0);
      if(in.size() == out.size()) {
	metasolve(in, out, offset, lim);
	in.clear();
	out.clear();
	offset.clear();
	lim.clear();
      }
    }
  }
  //cerr << "\\";
  
  return;
}
#define count asdhshdjsdfhjdhjgdfjkhld

Compilation message (stderr)

minerals.cpp: In function 'void metasolve(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
minerals.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i = 0; i < offset.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:54:7: warning: unused variable 'last' [-Wunused-variable]
   54 |   int last = 0, l = 0;
      |       ^~~~
minerals.cpp:54:17: warning: unused variable 'l' [-Wunused-variable]
   54 |   int last = 0, l = 0;
      |                 ^

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10