QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#699171 | #8783. Cherry Picking | Maybe_Tomorrow | WA | 0ms | 3644kb | C++20 | 2.0kb | 2024-11-02 02:49:27 | 2024-11-02 02:49:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> r(n), w(n);
for (int &i : r) cin >> i;
string s; cin >> s;
for (int i = 0; i < n; i++) w[i] = s[i] - '0';
vector<vector<int>> ones(1); // Start with one empty vector for the first "ones" interval
vector<pair<int, int>> maxzeros; // {max value in zero interval, corresponding ones index}
int curmaxzero = 0, oneidx = 0;
for (int i = 0; i < n; i++) {
if (w[i] == 0) {
curmaxzero = max(curmaxzero, r[i]);
if (i == n - 1 || w[i + 1] != 0) { // End of zero interval
maxzeros.push_back({curmaxzero, oneidx});
curmaxzero = 0;
}
} else {
if (ones.size() <= oneidx) {
ones.push_back(vector<int>()); // Add a new vector for each "ones" interval
}
ones[oneidx].insert(lower_bound(ones[oneidx].begin(), ones[oneidx].end(), r[i]), r[i]);
if (ones[oneidx].size() >= k) {
cout << "1\n";
return 0;
}
if (i == n - 1 || w[i + 1] != 1) { // End of ones interval
oneidx++;
}
}
}
int curmaxone = 0;
vector<int> mergedsize(oneidx);
sort(maxzeros.begin(), maxzeros.end());
for (const auto& interval : maxzeros) {
int leftone = interval.second - 1, rightone = interval.second;
int rightmerge = 0, leftmerge = 0;
// Check bounds before accessing `ones`
if (rightone < oneidx) {
rightmerge = ones[rightone].end() - upper_bound(ones[rightone].begin(), ones[rightone].end(), interval.first);
rightmerge -= mergedsize[rightone];
mergedsize[rightone] = rightmerge;
}
if (leftone >= 0) {
leftmerge = ones[leftone].end() - upper_bound(ones[leftone].begin(), ones[leftone].end(), interval.first);
leftmerge -= mergedsize[leftone];
mergedsize[leftone] = leftmerge;
}
curmaxone += leftmerge + rightmerge;
if (curmaxone >= k) {
cout << interval.first + 1<< "\n";
return 0;
}
}
cout << "0\n";
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
5 2 1 2 3 4 5 01101
output:
1
result:
wrong answer expected '2', found '1'