Submission #631707

#	Time	Username	Problem	Language	Result	Execution time	Memory
631707		cadmiumsky	Minerals (JOI19_minerals)	C++14	75 / 100	39 ms	2652 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;

void Solve(int N) {
  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() - l);
      offset.push_back(l);
      //if(in.size() == out.size())
	//l = in.size();
    }
  }
  //cerr << "\\";
  for(int i = 0; i <= 15; 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]);
  }
  return;
}
#define count asdhshdjsdfhjdhjgdfjkhld

Compilation message (stderr)

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