QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674794#8783. Cherry Pickingucup-team5062#WA 0ms3816kbC++172.5kb2024-10-25 17:28:112024-10-25 17:28:11

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 17:28:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2024-10-25 17:28:11]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'