oj.uz

Submission #693020

# Submission time Handle Problem Language Result Execution time Memory
693020 2023-02-02T09:06:18 Z safaricola Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2813 ms 700 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 496 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 20 ms 380 KB Output is correct
4 Correct 23 ms 372 KB Output is correct
5 Correct 13 ms 368 KB Output is correct
6 Correct 12 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 436 KB Output is correct
2 Correct 453 ms 444 KB Output is correct
3 Correct 723 ms 480 KB Output is correct
4 Correct 730 ms 576 KB Output is correct
5 Correct 414 ms 460 KB Output is correct
6 Correct 421 ms 340 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 648 KB Output is correct
2 Correct 1718 ms 696 KB Output is correct
3 Correct 2813 ms 612 KB Output is correct
4 Correct 2722 ms 700 KB Output is correct
5 Correct 1594 ms 684 KB Output is correct
6 Correct 1584 ms 560 KB Output is correct