Submission #915930

#	Time	Username	Problem	Language	Result	Execution time	Memory
915930		HorizonWest	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	43 ms	12000 KiB

ho_t2

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

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cerr << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

void solve()
{
    int n, m; cin >> n >> m; 
    string s, ref = "JOI"; cin >> s;
    vector <vector<int>> v(n + 1, vector <int> (ref.size(), 0));
    vector <int> c(257, -1);
    for(int i = 0; i < ref.size(); i++)
        c[ref[i]] = i;

    for(int i = 1; i <= n; i++)
    {
        v[i][c[s[i-1]]]++; 
        for(int j = 0; j < ref.size(); j++)
            v[i][j] += v[i-1][j]; 
    } 

    int ans = Inf; 

    for(int i = 1; i <= n; i++) if(s[i-1] == 'J')
    {
        int l = i - 1; 
        
        for(int j = 0; j < ref.size(); j++)
        {
            int x = c[ref[j]]; 

            if(v[n][x] - v[l][x] < m)
            { 
                l = Inf; 
                break;
            }

            int a = l, b = n+1;  

            while(abs(a - b) != 1)
            {
                int mid = (a + b) / 2; 

                if(v[mid][x] - v[l][x] >= m)
                    b = mid; 
                else 
                    a = mid; 
            } 

            l = b;
        } 

        ans = min(ans, (l - i + 1) - (3 * m)); 
    }

    cout << (ans > n ? -1 : ans) << endl; 
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < ref.size(); i++)
      |                    ~~^~~~~~~~~~~~
ho_t2.cpp:46:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 0; j < ref.size(); j++)
      |                        ~~^~~~~~~~~~~~
ho_t2.cpp:56:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int j = 0; j < ref.size(); j++)
      |                        ~~^~~~~~~~~~~~

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