Submission #797488

#	Time	Username	Problem	Language	Result	Execution time	Memory
797488		beaconmc	Minerals (JOI19_minerals)	C++14	100 / 100	313 ms	15384 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
 
typedef long long ll;
 
 
 
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
 
 
 
std::set<ll> machine;
int query(int a){
  if (machine.count(a)){
    machine.erase(a);
  }else{
    machine.insert(a);
  }
  return Query(a);
}
 
void Solve(int N) {
  ll fuck = 0;
  using namespace std;
  vector<vector<ll>> top;
  vector<vector<ll>> bot;
   
  top.push_back({});
  bot.push_back({});
   
   
  ll cur = 0;
   
  FOR(i,1, 2*N+1){
   
    ll result = query(i);
    if (result == cur + 1){
      cur++;
      top[0].push_back(i);
    }else{
      bot[0].push_back(i);
    }
  }


   
  ll sus = 0;
   
  while (!(top.size() == bot.size() && bot.size() == N)){

    sus++;
   
    vector<vector<ll>> temp;
    for (auto&i : bot){
      if (i.size() == 1){
        temp.push_back(i);
        continue;
      }
      long double ratio = 2;
      if (i.size() >= 8) ratio = 2.58;
      


   
      vector<ll> temp2;
      ll cutoff = (long double) i.size() / ratio;




      FOR(j,0,cutoff){
        temp2.push_back(i[j]);
      }
      temp.push_back(temp2);
      temp2.clear();
   
      FOR(j, cutoff, i.size()){
        temp2.push_back(i[j]);
      }
      temp.push_back(temp2);
    }
    bot = temp;
    temp.clear();
   
   
   
   
   
    ll ind = 0;
   
   
   
    FOR(i,0,top.size()){

      ll tempflag = -1;


      if (sus%2 == 0){
        if (machine.count(bot[ind][0])) tempflag = (sus + 1)%2;
        else tempflag = sus%2;
      }else{
        if (machine.count(bot[ind][0])) tempflag = sus%2;
        else tempflag = (sus+1)%2;
      }
   
      if (top[i].size() == 1){
        ind += 1;
        temp.push_back(top[i]);
        continue;
      }


   
      vector<ll> first;
      vector<ll> second;
      ll curval = 0;
   

   
      for (auto&j : bot[ind]){
   
        curval = query(j);
   
      }
      ll idkman = top[i][top[i].size()-1];
      top[i].pop_back();

   
   
   
      for (auto&j : top[i]){
        ll result = query(j);
   
        if (result != curval){
          curval = result;
          first.push_back(j);
        }else{
          second.push_back(j);
        }
      }


      if (tempflag%2==1){
        
        if (first.size() != bot[ind].size()) first.push_back(idkman);
        else second.push_back(idkman);
        temp.push_back(first);
        temp.push_back(second);
      }
      else{

        if (second.size() != bot[ind].size()) second.push_back(idkman);
        else first.push_back(idkman);
        temp.push_back(second);
        temp.push_back(first);
   
      }
   
      ind += 2;
    }
   
    top = temp;
   
  }
   
  FOR(i,0,N){

   
    Answer((int) top[i][0],(int) bot[i][0]);
  }
   
   
   
   
   
 
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:51:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   while (!(top.size() == bot.size() && bot.size() == N)){
      |                                        ~~~~~~~~~~~^~~~
minerals.cpp:8:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   79 |       FOR(j, cutoff, i.size()){
      |           ~~~~~~~~~~~~~~~~~~~      
minerals.cpp:79:7: note: in expansion of macro 'FOR'
   79 |       FOR(j, cutoff, i.size()){
      |       ^~~
minerals.cpp:8:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   95 |     FOR(i,0,top.size()){
      |         ~~~~~~~~~~~~~~             
minerals.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR(i,0,top.size()){
      |     ^~~
minerals.cpp:25:6: warning: unused variable 'fuck' [-Wunused-variable]
   25 |   ll fuck = 0;
      |      ^~~~

• 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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10