Submission #922158

#	Time	Username	Problem	Language	Result	Execution time	Memory
922158		huutuan	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	285 ms	1116 KiB

dango3

#include "dango3.h"

#include <bits/stdc++.h>

using namespace std;

void Solve(int n, int m, vector<int> idx){
   if (m==1) return Answer(idx);
   int m1=m/2, m2=m-m1;
   int l=0, r=(int)idx.size()-1;
   while (l<=r){
      int mid=(l+r)>>1;
      if (Query(vector<int>(idx.begin(), idx.begin()+mid+1))>=m1) r=mid-1;
      else l=mid+1;
   }
   vector<int> _idx1(idx.begin(), idx.begin()+l+1);
   vector<int> idx2(idx.begin()+l+1, idx.end());
   vector<int> idx1;
   while (_idx1.size()){
      vector<int> tmp(idx1.begin(), idx1.end());
      int i=_idx1.back(); _idx1.pop_back();
      tmp.insert(tmp.end(), _idx1.begin(), _idx1.end());
      if (Query(tmp)>=m1) idx2.push_back(i);
      else idx1.push_back(i);
   }
   Solve(n, m1, idx1);
   Solve(n, m2, idx2);
}

void Solve(int n, int m){
   vector<int> idx;
   for (int i=1; i<=n*m; ++i) idx.push_back(i);
   Solve(n, m, idx);
}

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