Submission #140121

#	Time	Username	Problem	Language	Result	Execution time	Memory
140121		KLPP	Minerals (JOI19_minerals)	C++14	70 / 100	451 ms	5884 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;
}
void Work(vector<int> v1,vector<int> v2){
  /*if(v1.size()!=0){
    rep(i,0,v1.size()){
      cout<<v1[i]<<" ";
    }cout<<endl;
  }*/
  if(v1.size()==1){
    Answers.push_back(pair<int,int>(v1[0],v2[0]));
    return;
  }
  vector<int> v11,v12,v21,v22;
  rep(i,0,(int)v1.size()){
    if(2*i<(int)v1.size()){
      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;
  rep(i,0,(int)v2.size()){
    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) {
  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);
  }
}

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