QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#674794 | #8783. Cherry Picking | ucup-team5062# | WA | 0ms | 3816kb | C++17 | 2.5kb | 2024-10-25 17:28:11 | 2024-10-25 17:28:11 |
Judging History
answer
#include <set>
#include <array>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int solve(int N, int K, const vector<int>& R, const string& S) {
// step #1. check for K = 1 case
if (K == 1) {
int subans = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '1') {
subans = max(subans, R[i]);
}
}
return subans;
}
// step #2. sorting
vector<pair<int, int> > pack(N);
for (int i = 0; i < N; i++) {
pack[i] = make_pair(R[i], i);
}
sort(pack.begin(), pack.end());
pack.erase(unique(pack.begin(), pack.end()), pack.end());
// step #3. create set
set<array<int, 4> > s;
int spre = 0;
int zcnt = 0;
for (int i = 1; i <= N; i++) {
if (i == N || S[i] != S[i - 1]) {
s.insert({spre, i, i - spre, int(S[i - 1] - '0')});
if (S[i - 1] == '1' && i - spre >= K) {
zcnt++;
}
spre = i;
}
}
// step #4. calculate answer
int ans = (zcnt >= 1 ? *min_element(R.begin(), R.end()) : 0);
int tpre = 0;
for (int i = 1; i <= N; i++) {
/*
for (array<int, 4> v : s) {
cout << "(" << v[0] << ", " << v[1] << ", " << v[2] << ", " << v[3] << ") ";
}
cout << endl;
*/
if (i == N || pack[i].first != pack[i - 1].first) {
for (int j = tpre; j < i; j++) {
set<array<int, 4> >::iterator it = --s.lower_bound({j + 1, -1, -1, -1});
array<int, 4> z = *it;
s.erase(it);
if (z[2] >= 2) {
if (z[3] == 1 && z[2] == K) {
zcnt--;
}
s.insert({z[0], z[1], z[2] - 1, z[3]});
} else {
it = s.lower_bound({j + 1, -1, -1, -1});
array<int, 4> zl, zr;
if (it != s.end()) {
zr = *it;
it = s.erase(it);
if (zr[3] == 1 && zr[2] >= K) {
zcnt--;
}
} else {
zr = {z[1], z[1], 0, z[3]};
}
if (it != s.begin()) {
zl = *(--it);
s.erase(it);
if (zl[3] == 1 && zl[2] >= K) {
zcnt--;
}
} else {
zl = {z[0], z[0], 0, z[3]};
}
s.insert({zl[0], zr[1], zl[2] + zr[2], zr[3]});
if (zr[3] == 1 && zl[2] + zr[2] >= K) {
zcnt++;
}
}
}
if (zcnt >= 1 && i != N) {
ans = pack[i].first;
}
tpre = i;
}
}
return ans;
}
int main() {
// step #1. input
cin.tie(nullptr);
ios::sync_with_stdio(false);
int N, K;
cin >> N >> K;
vector<int> R(N);
for (int i = 0; i < N; i++) {
cin >> R[i];
}
string S;
cin >> S;
int ans = solve(N, K, R, S);
cout << ans << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3624kb
input:
5 3 8 3 5 2 7 10101
output:
0
result:
wrong answer expected '5', found '0'