oj.uz

Submission #753807

# Submission time Handle Problem Language Result Execution time Memory
753807 2023-06-06T05:41:09 Z vjudge1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 384 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]++;
    }
    int mn=INT_MAX;
    for (int i=0;i<s.size()-1;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())
            mn=min(mn,r-i);
    }
    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:19: 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 |     for (int i=0;i<s.size()-1;i++) {
      |                  ~^~~~~~~~~~~
ho_t2.cpp:72: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]
   72 |         if (r!=s.size())
      |             ~^~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -