Submission #796336

#	Time	Username	Problem	Language	Result	Execution time	Memory
796336		beaconmc	Minerals (JOI19_minerals)	C++14	85 / 100	276 ms	13980 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) {
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() >= 10) ratio = 2.5;

    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 (top[i].size() == 1){
      ind += 1;
      temp.push_back(top[i]);
      continue;
    }


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

    if (sus%2 == 0){
      if (machine.count(bot[ind][0])) tempflag = (sus + 1)%2;
      else tempflag = sus;
    }else{
      if (machine.count(bot[ind][0])) tempflag = sus;
      else tempflag = (sus+1)%2;
    }

    for (auto&j : bot[ind]){

      curval = query(j);

    }



    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){
      temp.push_back(first);
      temp.push_back(second);
    }
    else{
      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:48:49: 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]
   48 | 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++)
......
   68 |     FOR(j, cutoff, i.size()){
      |         ~~~~~~~~~~~~~~~~~~~        
minerals.cpp:68:5: note: in expansion of macro 'FOR'
   68 |     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++)
......
   84 |   FOR(i,0,top.size()){
      |       ~~~~~~~~~~~~~~               
minerals.cpp:84:3: note: in expansion of macro 'FOR'
   84 |   FOR(i,0,top.size()){
      |   ^~~

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