oj.uz

Submission #692844

# Submission time Handle Problem Language Result Execution time Memory
692844 2023-02-02T06:28:25 Z safaricola Super Dango Maker (JOI22_dango3) C++17
22 / 100
 1968 ms 636 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;
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.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 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 340 KB Output is correct
2 Correct 17 ms 380 KB Output is correct
3 Correct 27 ms 364 KB Output is correct
4 Correct 26 ms 340 KB Output is correct
5 Correct 14 ms 376 KB Output is correct
6 Correct 15 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 492 KB Output is correct
2 Correct 508 ms 488 KB Output is correct
3 Correct 782 ms 528 KB Output is correct
4 Correct 762 ms 428 KB Output is correct
5 Correct 472 ms 552 KB Output is correct
6 Correct 461 ms 560 KB Output is correct

Subtask #4
0 / 78.0

# Verdict Execution time Memory Grader output
1 Incorrect 1968 ms 636 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -