Submission #693020

#	Time	Username	Problem	Language	Result	Execution time	Memory
693020		safaricola	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2813 ms	700 KiB

dango3

#include "dango3.h"
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
using namespace std;
int ind=0,MM,NN;
vector<int> l[30];
bool check(int m, int x){
  vector<int> aa;
  rep(i,x-1){
    aa.pb(i);
  }
  for(int i=m+1; i<=ind; i++){
    for(auto it: l[i]){
      aa.pb(it);
      //cout<<it<<' ';
    }
    //cout<<i<<endl;
  }
  
  int ann=Query(aa);
  //cout<<ann<<endl;
  if(ann==MM-m){ // if it is below
    return false; // find the higher range
  }
  // if correct or above
  return true; // find the lower range
}
int search(int x){
  int s=0, e=ind, mid;
  while(mid=(e+s)/2, e-s>1){
    int temp=check(mid,x);
    //cout<<"mid: "<<mid<<' '<<temp<<endl;
    if(temp) s=mid;
    else e=mid;
  }
  return e;
}
bool chk(int m, int x){
  vector<int> xx;
  rep(i,m){
    xx.pb(i);
  }
  if(Query(xx)>=x)return false;
  return true;
}
int sear(int x){
  int s=0, e=NN*MM, mid;
    while(mid=(e+s)/2, e-s>1){
      int temp=chk(mid,x);
      if(temp) s=mid;
      else e=mid;
    }
    return e;
}

void Solve(int N, int M) {
  vector<int> x;
  MM=M;
  NN=N;
  bool a[N*M+5];
  rep(i,N*M)a[i]=0;
  rep(i,M){
    //cout<<sear(i)<<endl;
    a[sear(i)]=1;
  }
  //rep(i,N*M)cout<<a[i]<<' ';
  //cout<<endl;
  for(int i=N*M; i>0; i--){
    if(a[i]){
      ind++;
      //cout<<a[i]<<a[i-1]<<endl;
      //cout<<i<<">>"<<ind<<endl;
      l[ind].pb(i);
    }else{
      int temp=search(i);
      //cout<<i<<">>>"<<temp<<endl;
      l[temp].pb(i);
    }

  }
  //cout<<"-----------------";
  rep(i,M){
      vector<int> aa;
    for(auto it: l[i]){
      //cout<<it<<' ';
      aa.pb(it);
    }
    Answer(aa);
    //cout<<endl;
  }
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78