# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
541538 | 2022-03-23T18:06:45 Z | NyanCatTW1 | JJOOII 2 (JOI20_ho_t2) | C++17 | 1 ms | 328 KB |
#include <iostream> #include <vector> #include <deque> using namespace std; typedef long long LL; #define rangeLen(x) (partRange[x].second - partRange[x].first) int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, K; string SStr; cin >> N >> K >> SStr; vector<int> S(SStr.size()); vector<vector<int> > charIndexes(3); for (int i = 0; i < SStr.size(); i++) { switch (SStr[i]) { case 'J': S[i] = 0; charIndexes[0].push_back(i); break; case 'O': S[i] = 1; charIndexes[1].push_back(i); break; case 'I': S[i] = 2; charIndexes[2].push_back(i); break; } } int ans = 1000000; vector<pair<int, int> > partRange(3); vector<int> partEndIndex(3); int R = -1; for (int L = 0; L < S.size(); L++) { if (L) { int toRemove = S[L - 1]; if (rangeLen(toRemove) != 0 && charIndexes[toRemove][partRange[toRemove].first] == L - 1) { partRange[toRemove].first++; if (rangeLen(toRemove) >= K) { partEndIndex[toRemove] = charIndexes[toRemove][partRange[toRemove].first + K - 1]; } } } for (int k = 0; k < 3; k++) { if (k) { while (rangeLen(k) != 0 && charIndexes[k][partRange[k].first] < partEndIndex[k - 1]) { partRange[k].first++; } } while (R + 1 != S.size() && rangeLen(k) < K) { R++; partRange[S[R]].second++; if (rangeLen(S[R]) == K) { partEndIndex[S[R]] = charIndexes[S[R]][partRange[S[R]].second - 1]; } } if (rangeLen(k) < K) { goto end; } } ans = min(ans, (R - L + 1) - K * 3); } end: if (ans == 1000000) ans = -1; cout << ans << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 328 KB | Output is correct |
8 | Incorrect | 1 ms | 212 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 328 KB | Output is correct |
8 | Incorrect | 1 ms | 212 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 328 KB | Output is correct |
8 | Incorrect | 1 ms | 212 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |