Submission #503566

#	Time	Username	Problem	Language	Result	Execution time	Memory
503566		gaspar	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	15 ms	4020 KiB

ho_t2

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n, k;
pair <int, int> a[200005], b[200005];
string s;
deque <int> dq;

int main() {
    cin >> n >> k >> s;
    s = ' ' + s;
    int rez = n + 1;
    a[0] = {1e9, 0};
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1];
        if (s[i] != 'J')
            continue;
        if (dq.size() == k)
            dq.pop_front();
        dq.push_back(i);
        if (dq.size() == k)
            a[i] = {dq.back() - dq.front() - (k - 1), dq.back() + 1};
    }
    dq.clear();
    b[n + 1] = {1e9, 0};
    for (int i = n; i >= 1; --i) {
        b[i] = b[i + 1];
        if (s[i] != 'I')
            continue;
        if (dq.size() == k)
            dq.pop_back();
        dq.push_front(i);
        if (dq.size() == k)
            b[i] = {dq.back() - dq.front() - (k - 1), dq.front() - 1};
    }
    dq.clear();
    for (int i = 1; i <= n; ++i) {
        if (s[i] != 'O')
            continue;
        if (dq.size() == k)
            dq.pop_front();
        dq.push_back(i);
        if (dq.size() == k) {
            int nrj = a[dq.front() - 1].first, posj = a[dq.front() - 1].second;
            int nri = b[dq.back() + 1].first, posi = b[dq.back() + 1].second;
            if (nrj != 1e9 && nri != 1e9)
                rez = min(rez, nri + nrj + dq.back() - dq.front() + 1 - k + posi - dq.back() + dq.front() - posj);
        }
    }
    if (rez == n + 1)
        rez = -1;
    cout << rez;
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:20:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |         if (dq.size() == k)
      |             ~~~~~~~~~~^~~~
ho_t2.cpp:23:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |         if (dq.size() == k)
      |             ~~~~~~~~~~^~~~
ho_t2.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if (dq.size() == k)
      |             ~~~~~~~~~~^~~~
ho_t2.cpp:35:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         if (dq.size() == k)
      |             ~~~~~~~~~~^~~~
ho_t2.cpp:42:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         if (dq.size() == k)
      |             ~~~~~~~~~~^~~~
ho_t2.cpp:45:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         if (dq.size() == k) {
      |             ~~~~~~~~~~^~~~

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