Submission #631716

#	Time	Username	Problem	Language	Result	Execution time	Memory
631716		cadmiumsky	Minerals (JOI19_minerals)	C++14	40 / 100	36 ms	2460 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; }

const int nmax = 43e3 + 5;
namespace Q {
  int is[nmax * 2];
  int last = 0, curr = 0;
  bool isdiff() {return last != curr; }
  bool query(int x) { is[x] ^= 1; last = curr; curr = Query(x); return isdiff(); }
}
using namespace Q;
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 < out.size(); j++) {
      if(offset[j] + (1 << i) >= lim[j])
	continue;
      if(!query(out[j]))	
	offset[j] += (1 << i);
    }
  }
  for(int i = 0; i < out.size(); i++) {
    //cerr << "#" << out[i] << ' ' << in[offset[i]] << '\n';
    Answer(in[offset[i]], out[i]);
    in[offset[i]] = -1;
  }
  for(int i = 0; i < in.size(); i++) {
    if(in[i] == -1)
      swap(in[i], in.back()),
      in.pop_back(),
      i--;
  }
  for(auto x : in)
    if(!is[x])
      query(x);
  out.clear();
  offset.clear();
  lim.clear();
}

const int limit = 8191;

void Solve(int N) {
  lg[0] = -1;
  int cnt = 0;
  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);
      cnt++;
      //cerr << "^ " <<x  << ' ' << in.size() << ' ' << out.size() << '\n';
      if(in.size() == out.size() || cnt > limit) {
	metasolve(in, out, offset, lim);
	cnt = 0;
      }
    }
  }
  //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:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int j = 0; j < out.size(); j++) {
      |                    ~~^~~~~~~~~~~~
minerals.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int i = 0; i < out.size(); i++) {
      |                  ~~^~~~~~~~~~~~
minerals.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i = 0; i < in.size(); i++) {
      |                  ~~^~~~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:72:7: warning: unused variable 'last' [-Wunused-variable]
   72 |   int last = 0, l = 0;
      |       ^~~~
minerals.cpp:72:17: warning: unused variable 'l' [-Wunused-variable]
   72 |   int last = 0, l = 0;
      |                 ^

• 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