oj.uz

Submission #753802

# Submission time Handle Problem Language Result Execution time Memory
753802 2023-06-06T05:34:23 Z vjudge1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 2000 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 or ps[1][z2] - ps[1][z1] < k or 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]++;
    }
    int l = 0, r = 1, mn = INT_MAX;
    while (r < s.size()) {
        while (r < s.size() and !ch(l,r))
            r++;
        while (l < r and ch(l,r)) {
            mn = min(mn, r - l);
            l++;
        }
        if (l==r and r==s.size()-1)
            break;
    }
    if (mn==INT_MAX)
        cout << -1;
    else
        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:63:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while (r < s.size()) {
      |            ~~^~~~~~~~~~
ho_t2.cpp:64:18: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (r < s.size() and !ch(l,r))
      |                ~~^~~~~~~~~~
ho_t2.cpp:70: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]
   70 |         if (l==r and r==s.size()-1)
      |                      ~^~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -