oj.uz

Submission #780060

# Submission time Handle Problem Language Result Execution time Memory
780060 2023-07-12T06:17:06 Z PoonYaPat Super Dango Maker (JOI22_dango3) C++17
100 / 100
 4680 ms 816 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;

int n,m;

bool check(int want, vector<int> temp, vector<int> a) {
  vector<int> h;
  for (auto s : a) {
    auto it=lower_bound(temp.begin(),temp.end(),s);
    if (it==temp.end() || *it!=s) h.push_back(s);
  }
  if (Query(h)>=want) return true;
  else return false;
}

void find(int l, int r, vector<int> a) {
  if (l==r) Answer(a);
  else {
    int mid=(l+r)/2;
    vector<int> temp1,temp2;

    for (auto s : a) {
      temp1.push_back(s);
      if (!check(r-mid,temp1,a)) {
        temp1.pop_back();
        temp2.push_back(s);
      }
    }

    find(l,mid,temp1);
    find(mid+1,r,temp2);
  }
}

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

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 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 23 ms 340 KB Output is correct
2 Correct 23 ms 420 KB Output is correct
3 Correct 25 ms 340 KB Output is correct
4 Correct 26 ms 428 KB Output is correct
5 Correct 21 ms 416 KB Output is correct
6 Correct 20 ms 312 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1027 ms 668 KB Output is correct
2 Correct 1022 ms 548 KB Output is correct
3 Correct 953 ms 552 KB Output is correct
4 Correct 945 ms 556 KB Output is correct
5 Correct 930 ms 552 KB Output is correct
6 Correct 936 ms 552 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 4680 ms 724 KB Output is correct
2 Correct 4659 ms 700 KB Output is correct
3 Correct 4371 ms 720 KB Output is correct
4 Correct 4377 ms 816 KB Output is correct
5 Correct 4238 ms 700 KB Output is correct
6 Correct 4250 ms 704 KB Output is correct