oj.uz

Submission #922158

# Submission time Handle Problem Language Result Execution time Memory
922158 2024-02-05T07:45:14 Z huutuan Super Dango Maker (JOI22_dango3) C++17
100 / 100
 285 ms 1116 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 696 KB Output is correct
2 Correct 39 ms 604 KB Output is correct
3 Correct 71 ms 688 KB Output is correct
4 Correct 71 ms 704 KB Output is correct
5 Correct 24 ms 604 KB Output is correct
6 Correct 27 ms 900 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 752 KB Output is correct
2 Correct 164 ms 892 KB Output is correct
3 Correct 285 ms 1116 KB Output is correct
4 Correct 272 ms 1108 KB Output is correct
5 Correct 90 ms 848 KB Output is correct
6 Correct 86 ms 864 KB Output is correct