Submission #137959

#	Time	Username	Problem	Language	Result	Execution time	Memory
137959		Bohoty	Minerals (JOI19_minerals)	C++14	80 / 100	378 ms	16848 KiB

minerals

#include "minerals.h"
//#include "grader.cpp"
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
int inside[mxN], tot;
int get(int x){
  if(inside[x])
  tot--;
  else
  tot++;
  inside[x] ^= 1;
  return tot - Query(x);
}
void goKill(set<int> a, set<int> b, bool aInside, bool bInside){
  // cout << a.size() << '\n';
  if(a.size() == 2){
      int cur = get(*a.begin());
      int cur2 = get(*b.begin());
      if(aInside){
        if(cur == cur2){
          Answer(*a.begin(),*b.begin());
          Answer(*a.rbegin(),*b.rbegin());
        } else {
          Answer(*a.begin(),*b.rbegin());
          Answer(*a.rbegin(),*b.begin());
        }
      }
    else {
      if(cur != cur2){
        Answer(*a.begin(),*b.begin());
        Answer(*a.rbegin(),*b.rbegin());
      } else {
        Answer(*a.begin(),*b.rbegin());
        Answer(*a.rbegin(),*b.begin());
      }
    }
    return;
  }
  if(a.size() == 1){
    Answer(*a.begin(), *b.begin());
    return;
  }
  std::vector<int> o;
  for(auto x : b)o.push_back(x);
  random_shuffle(o.begin(),o.end());
  int sz = a.size();
  set<int> x, y;
  int b4;
  int take = ceil(0.36 * sz);
  if(!aInside)take = sz - take;
  for(int j = 1; j <= take; j++){
    int v = *a.begin();
    a.erase(v);
    x.insert(v);
    b4 = get(v);
  }
  b.clear();
  for(auto it : o){
    if(x.size() == y.size())b.insert(it);
    else {
    int v = get(it);
    if((!aInside && v != b4)||(aInside && v == b4)){
      y.insert(it);
    } else b.insert(it);
    b4 = v;
    }
  }
  goKill(x,y,aInside^1,bInside^1);
  goKill(a,b,aInside,bInside^1);
}
void Solve(int N) {
  srand(time(0));
  int n = N + N;
  set<int> a, b;
  int b4 = 0;
  for (int i = 1; i <= n; i++) {
    int x = get(i);
    if(x > b4){
      a.insert(i);
    } else {
      b.insert(i);
    }
    b4 = x;
  }
  // cout << a.size() << ' ' << b.size() << '\n';

  goKill(a, b, 1, 1);

}

Compilation message (stderr)

minerals.cpp: In function 'void goKill(std::set<int>, std::set<int>, bool, bool)':
minerals.cpp:64:29: warning: 'b4' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if((!aInside && v != b4)||(aInside && v == b4)){
        ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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