Submission #1217034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217034		noyancanturk	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	178 ms	644 KiB

dango3

#include "dango3.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

void Solve(int n,int m){
  srand(time(0));
  int p[n*m];
  for(int i=0;i<n*m;i++){
    p[i]=i+1;
  }
  int ok[n*m+1]{};
  int left=n*m;
  random_shuffle(p,p+n*m);
  while(left){
    if(left==n){
      vector<int>ans;
      for(int i=0;i<n*m;i++){
        if(!ok[p[i]])ans.pb(p[i]);
      }
      Answer(ans);
      break;
    }
    int l=2*n,r=left,res=left;
    while(l<=r){
      int mid=l+r>>1;
      vector<int>toask;
      for(int i=0;i<n*m;i++){
        if(!ok[p[i]]){
          toask.pb(p[i]);
        }
        if(toask.size()==mid)break;
      }
      int k=Query(toask);
      if(1<=k){
        res=mid;
        r=mid-1;
      }else{
        l=mid+1;
      }
    }
    vector<int>vv;
    for(int i=0;i<n*m;i++){
      if(!ok[p[i]])vv.pb(p[i]);
      if(vv.size()==res)break;
    }
    auto f=[&](int x,int y,int z){
      vector<int>toask;
      for(int j=0;j<vv.size();j++){
        if(x==j||y==j||z==j)continue;
        toask.pb(vv[j]);
      }
      return Query(toask);
    };
    for(int i=0;i<vv.size();){
      if(i+1==vv.size()){
        if(n<vv.size())vv.pop_back();
        else i++;
      }
      else if(i+2==vv.size()){
        if(f(i,-1,-1)){
          swap(vv[i],vv.back());
          vv.pop_back();
        }
        else i++;
      }else{
        if(f(i,i+1,i+2)){
          vv.erase(vv.begin()+i,vv.begin()+i+3);
        }else{
          if(f(i,-1,-1)){
            vv.erase(vv.begin()+i,vv.begin()+i+1);
          }else if(++i&&f(i,-1,-1)){
            vv.erase(vv.begin()+i,vv.begin()+i+1);
          }else if(++i&&f(i,-1,-1)){
            vv.erase(vv.begin()+i,vv.begin()+i+1);
          }
        }
      }
      if(vv.size()==n)break;
      // vector<int>toask;
      // for(int j=0;j<vv.size();j++){
      //   if(i==j)continue;
      //   toask.pb(vv[j]);
      // }
      // int k=Query(toask);
      // if(k==1){
      //   swap(vv[i],vv.back());
      //   vv.pop_back();
      //   i--;
      // }
    }
    for(int i:vv){
      ok[i]=1;
    }
    Answer(vv);
    left-=n;
  }
}

// void Solve(int N, int M) {
//   std::vector<int> x(3);
//   x[0] = 1;
//   x[1] = 2;
//   x[2] = 3;
//   variable_example = Query(x);
//   for (int i = 0; i < M; i++) {
//     std::vector<int> a(N);
//     for (int j = 0; j < N; j++) {
//       a[j] = N * i + j + 1;
//     }
//     Answer(a);
//   }
// }

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