Submission #140191

#	Time	Username	Problem	Language	Result	Execution time	Memory
140191		KLPP	Minerals (JOI19_minerals)	C++14	90 / 100	613 ms	6512 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int n;
set<int> s;
int last_answer;
void clear(){
  trav(a,s){
    Query(a);
  }
}
vector<pair<int,int> >Answers;
int Query2(int x){
  //cout<<x<<endl;
  last_answer=Query(x);
  if(s.find(x)==s.end()){
    s.insert(x);
  }else s.erase(x);
  return last_answer;
}
int ABS(int x){
  if(x>0)return x;
  return -x;
}
void Work(vector<int> v1,vector<int> v2){
  /*if(v1.size()!=0){
    int toggled=0;
    rep(i,0,v1.size()){
      if(s.find(v1[i])!=s.end())toggled++;
    }
    if(toggled!=v1.size() && toggled!=0)cout<<"ERR"<<endl;
  }*/
  /*rep(i,0,v1.size())cout<<v1[i]<<" ";
  cout<<endl;*/
  if(v1.size()==1){
    //cout<<v2.size()<<endl;
    Answers.push_back(pair<int,int>(v1[0],v2[0]));
    return;
  }
  int TOGGLE1=0;
  int TOGGLE2=0;
  rep(i,0,v1.size()){
    if(s.find(v1[i])!=s.end())TOGGLE1++;
  }
  rep(i,0,v2.size()){
    if(s.find(v2[i])!=s.end())TOGGLE2++;
  }
  if(ABS(TOGGLE2*2-v2.size())<ABS(TOGGLE1*2-v1.size())){
    swap(v1,v2);
  }
  vector<int> v11,v12,v21,v22;
  int mid=0;
  int toggled=0;
  rep(i,0,v1.size()){
    if(s.find(v1[i])!=s.end())toggled++;
  }
  if(toggled==0){
    mid=v1.size()/2;
  }else mid=(v1.size()+1)/2;
  rep(i,0,(int)v1.size()){
    if(i<mid){
      v11.push_back(v1[i]);
      if(s.find(v1[i])==s.end()){
	Query2(v1[i]);
      }
    }else{
      v12.push_back(v1[i]);
      if(s.find(v1[i])!=s.end()){
	Query2(v1[i]);
      }
    }
  }
  int LST=last_answer;
  //random_shuffle(v2.begin(),v2.end());
  rep(i,0,(int)v2.size()){
    if(v21.size()==v11.size()){
      v22.push_back(v2[i]);
    }else{
      if(v22.size()==v12.size()){
	v21.push_back(v2[i]);
      }else{
	if(Query2(v2[i])==LST){
	  v21.push_back(v2[i]);
	}else{
	  v22.push_back(v2[i]);
	}
      }
    }
    LST=last_answer;
  }
  Work(v11,v21);
  Work(v12,v22);
}
void Solve(int N) {
  srand(1007);
  n=N;
  int Q=0;
  vector<int> v1,v2;
  last_answer=0;
  rep(i,1,2*n+1){
    if(Query2(i)==Q){
      //Query2(i);
      v2.push_back(i);
    }else{
      Q++;
      s.insert(i);
      v1.push_back(i);
    }
  }//cout<<Q<<endl;
  Work(v1,v2);
  rep(i,0,(int)Answers.size()){
    //cout<<Answers[i].first<<" "<<Answers[i].second<<endl;
    Answer(Answers[i].first,Answers[i].second);
  }
}

Compilation message (stderr)

minerals.cpp: In function 'void Work(std::vector<int>, std::vector<int>)':
minerals.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
minerals.cpp:46:7:
   rep(i,0,v1.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:46:3: note: in expansion of macro 'rep'
   rep(i,0,v1.size()){
   ^~~
minerals.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
minerals.cpp:49:7:
   rep(i,0,v2.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:49:3: note: in expansion of macro 'rep'
   rep(i,0,v2.size()){
   ^~~
minerals.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
minerals.cpp:58:7:
   rep(i,0,v1.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:58:3: note: in expansion of macro 'rep'
   rep(i,0,v1.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: 5 / 5
• Subtask 9: 0 / 10