# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
940848 | 2024-03-07T18:44:05 Z | borisAngelov | Super Dango Maker (JOI22_dango3) | C++17 | 574 ms | 992 KB |
#include "dango3.h" #include <bits/stdc++.h> using namespace std; const int maxn = 10005; const int maxm = 30; int n, m; vector<int> ans[maxm]; void divideAndConquer(vector<int> indexes, int groups) { if (indexes.size() == n) { Answer(indexes); return; } int l = 0; int r = indexes.size() - 1; while (l <= r) { int mid = (l + r) / 2; vector<int> toQuery; for (int i = 0; i <= mid; ++i) { toQuery.push_back(indexes[i]); } if (Query(toQuery) >= groups / 2) { r = mid - 1; } else { l = mid + 1; } } int splitPos = l; vector<int> toLeft; vector<int> toRight; for (int i = 0; i <= splitPos; ++i) { toLeft.push_back(indexes[i]); } for (int i = splitPos + 1; i < indexes.size(); ++i) { toRight.push_back(indexes[i]); } vector<int> compressedLeft; vector<bool> removed(indexes.size(), false); for (int i = 0; i < toLeft.size(); ++i) { vector<int> toQuery; for (int j = 0; j < toLeft.size(); ++j) { if (i != j && removed[j] == false) { toQuery.push_back(toLeft[j]); } } if (Query(toQuery) == groups / 2) { toRight.push_back(toLeft[i]); removed[i] = true; } else { compressedLeft.push_back(toLeft[i]); } } toLeft = compressedLeft; sort(toLeft.begin(), toLeft.end()); sort(toRight.begin(), toRight.end()); divideAndConquer(toLeft, groups / 2); divideAndConquer(toRight, groups - groups / 2); } void Solve(int N, int M) { n = N; m = M; vector<int> all; for (int i = 1; i <= n * m; ++i) { all.push_back(i); } divideAndConquer(all, m); }
Compilation message
# | 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 | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 520 KB | Output is correct |
2 | Correct | 5 ms | 348 KB | Output is correct |
3 | Correct | 7 ms | 524 KB | Output is correct |
4 | Correct | 7 ms | 348 KB | Output is correct |
5 | Correct | 3 ms | 348 KB | Output is correct |
6 | Correct | 3 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 94 ms | 672 KB | Output is correct |
2 | Correct | 98 ms | 600 KB | Output is correct |
3 | Correct | 142 ms | 668 KB | Output is correct |
4 | Correct | 145 ms | 604 KB | Output is correct |
5 | Correct | 47 ms | 648 KB | Output is correct |
6 | Correct | 54 ms | 660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 348 ms | 780 KB | Output is correct |
2 | Correct | 364 ms | 848 KB | Output is correct |
3 | Correct | 545 ms | 852 KB | Output is correct |
4 | Correct | 574 ms | 848 KB | Output is correct |
5 | Correct | 172 ms | 856 KB | Output is correct |
6 | Correct | 188 ms | 992 KB | Output is correct |