oj.uz

Submission #753808

# Submission time Handle Problem Language Result Execution time Memory
753808 2023-06-06T05:48:27 Z vjudge1 JJOOII 2 (JOI20_ho_t2) C++14
0 / 100
 1 ms 340 KB 
// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;

const ll INF = LONG_MAX;
const int N =  2e6;
const int M = 1e9 + 7;
const ll HZ = 998244353;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;

int n,k,ps[3][N];
string s;

int find_pos(int L,int R,int val) {
    int l=L,r=R;
    while (l+1<r) {
        int mid=(l+r)/2;
        if (ps[val][mid]-ps[val][L]<k)
            l=mid;
        else
            r=mid;
    }
    return r;
}

bool ch(int l,int r) {
    int z1 = find_pos(l, r, 0), z2 = find_pos(z1, r, 1), z3 = find_pos(z2, r, 0);
    return ps[0][z1] - ps[0][l] >= k and ps[1][z2] - ps[1][z1] >= k and ps[2][z3] - ps[2][z2] >= k;
}

void solve() {
    s += ' ';
    string t;
    cin >> n >> k >> t;
    s += t;
    for (int i = 1; i < s.size(); i++) {
        for (int j = 0; j < 3; j++)
            ps[j][i] = ps[j][i - 1];
        if (s[i] == 'J')
            ps[0][i]++;
        if (s[i] == 'O')
            ps[1][i]++;
        if (s[i] == 'I')
            ps[2][i]++;
    }
    if (!ch(0,s.size()-1)) {
        cout << -1;
        return;
    }
    int mn = INT_MAX;
    for (int i = 0; i < s.size(); i++) {
        int l = i, r = s.size();
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (ch(i, mid))
                r = mid;
            else
                l = mid;
        }
        if (r == s.size())
            break;
        mn = min(mn, r - i);
    }
    cout << mn - k * 3;
}

signed main() {
    // freopen("262144.in", "r", stdin);
    // freopen("262144.out", "w", stdout);
    kanagattandirilmagandiktarinizdan
    int test = 1;
    // cin >> test;
    for (int i=1;i<=test;i++) {
        // cout << "Case " << i << ':' << '\n';
        solve();
        // cout << '\n';
    }
    return 0;
}

Compilation message

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 1; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
ho_t2.cpp:67:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
ho_t2.cpp:76:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if (r == s.size())
      |             ~~^~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -