Submission #692844

#	Time	Username	Problem	Language	Result	Execution time	Memory
692844		safaricola	Super Dango Maker (JOI22_dango3)	C++17	22 / 100	1968 ms	636 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;
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;
}

void Solve(int N, int M) {
  vector<int> x;
  int a[N*M+5];
MM=M;
  rep(i,N*M-2){
    x.pb(i);
    if(i<N){
      a[i]=0;
    }
    else
    a[i]=Query(x);
  }
  a[0]=0;
  a[N*M-1]=M-1;
  a[N*M]=M;
  for(int i=N*M; i>0; i--){
    if(a[i]!=a[i-1]){
      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: 0 / 78