Submission #988495

#	Time	Username	Problem	Language	Result	Execution time	Memory
988495		_callmelucian	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	47 ms	2132 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

vector<int> J, O, I;
int level;

bool ok (int l, int r) {
    int curJ = lower_bound(all(J), l) - J.begin();
    if (curJ + level > J.size()) return 0;
    int curO = lower_bound(all(O), J[curJ + level - 1]) - O.begin();
    if (curO + level > O.size()) return 0;
    int curI = lower_bound(all(I), O[curO + level - 1]) - I.begin();
    if (curI + level > I.size()) return 0;
    return I[curI + level - 1] <= r;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n >> level;
    string s; cin >> s;

    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'J') J.push_back(i);
        if (s[i - 1] == 'O') O.push_back(i);
        if (s[i - 1] == 'I') I.push_back(i);
    }

    int ans = INT_MAX;
    for (int l = 1, r = 1; r <= n; r++) {
        while (l < r && ok(l + 1, r)) l++;
        if (ok(l, r))
            ans = min(ans, r - l + 1 - 3 * level);
    }
    cout << (ans == INT_MAX ? -1 : ans);

    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'bool ok(int, int)':
ho_t2.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (curJ + level > J.size()) return 0;
      |         ~~~~~~~~~~~~~^~~~~~~~~~
ho_t2.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if (curO + level > O.size()) return 0;
      |         ~~~~~~~~~~~~~^~~~~~~~~~
ho_t2.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if (curI + level > I.size()) return 0;
      |         ~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87