Submission #753795

#	Time	Username	Problem	Language	Result	Execution time	Memory
753795		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	320 KiB

ho_t2

#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define run_faster ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); ios_base::sync_with_stdio(0); cin.tie(nullptr);

using namespace std;
const double PI = 3.141592653589793;
const long long INF = 2e18;
const long long inf = 2147483647;

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

// ll gcd( ll a, ll b ) {
//     return b? gcd( b, a%b ): a;
// }
// ll lcm( ll a, ll b ) {
//     return a/gcd( a,b ) * b;
// }
// ll bp( ll x, ll a ) {
//     ll res = 1;
//     while( n ) {
//         if( n&1 )
//             res *= a;
//         a *= a;
//         n >>= 1;
//     }
//     return res;
// }


// const int N = 1e5+1;
// vector<vector<int>> g(N);
// vector<vector<int>> r(N);
// vector<bool> used(N);
// vector<ll> comp;
// vector<ll> order;

// void dfs2( int x ) {
//     used[x] = 1; // graph is directed, so
//     for( int to: r[x] ) { // if || g[x].pb(y) ||,
//         if( !used[to] ) { // then || r[y].pb(x) ||
//             dfs2(to);
//         }
//     }
//     comp.pb(x);
// }

// void dfs( int v ) {
//     used[v] = 1;
    
//     for( int to: g[v] ) {
//         if( !used[to] ) {
//             dfs(to);
//         }
//     }
//     order.pb(v);
// }

// const int N = 1e5+1;

// vector<int> p(N);

// int get(int v) {
//     return v == p[v]? v: p[v] = get(p[v]);
// }

// void unite( int a, int b ) {
//     a = get(a);
//     b = get(b);
//     if( rand()&1 )
//         swap( a,b );
//     if( a!=b )
//         p[a]=b;
// }

// vector<pair<ll,pair<int,int>>> g;
// vector<vector<int>> graph(N);
// vector<bool> used(N);

// void dfs( int v ) {
//     used[v] = 1;
    
//     for( int to: graph[v] ) {
//         if( !used[to] ) {
//             dfs(to);
//         }
//     }
// }

// const int N = 2e5+1;
// int parent[N], sz[N];

// void make_set( int v ) {
//     parent[v] = v;
//     sz[v] = 1;
// }

// int find_set( int v ) {
//     if( v == parent[v] )
//         return v;
//     return parent[v] = find_set(parent[v]);
// }

// void union_sets( int x, int y ) {
//     x = find_set( x );
//     y = find_set( y );
//     if( x != y ) {
//         if( sz[x] < sz[y] )
//             swap(x,y);
//         parent[y] = x;
//         sz[x]+=sz[y];
//     }
// }

// const int N = 2e5+1;
// int p[N];
// int sz[N];
// int mn[N];
// int mx[N];

// int get( int v ) {
//     return p[v] == v? v: p[v] = get(p[v]);
// }

// void unions( int a, int b ) {
//     a = get(a);
//     b = get(b);
    
//     if( rand()&1 ) {
//         swap(a,b);
//     }
//     if( a!=b ) {
//         p[a] = b;
//         sz[b]+=sz[a];
//         mn[b] = min(mn[a],mn[b]);
//         mx[b] = max(mx[a],mx[b]);
//     }
// }

signed main()
{
    // freopen( "input.in" , "r" , stdin );
    // freopen( "output.out" , "w" , stdout );
    run_faster;
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    int pj = -1, po = -1, pi = -1;
    int cj = 0, co = 0, ci = 0;
    ll sum = 0;
    
    for( int i = 0; i < n; i++ ) {
        if( s[i] == 'J') {
            if( pj != -1 ) {
                sum += i - pj - 1;
            }
            pj = i;
            cj++;
        }
        if( cj == k ) {
            break;
        }
    }
    if( cj == k ) {
        for( int i = pj+1; i < n; i++ ) {
            if( s[i] == 'O') {
                if( po != -1 ) {
                    sum += i-po-1;
                }
                po = i;
                co++;
            }
            if( co == k ) {
                break;
            }
        }
        if( co == k ) {
            for( int i = po+1; i < n; i++ ) {
                if( s[i] == 'I') {
                    if( pi != -1 ) {
                        sum += i-pi-1;
                    }
                    pi = i;
                    ci++;
                }
                if( ci == k ) {
                    break;
                }
            }
            if( ci == k ) {
                cout << sum;
            } else {
                cout << -1;
            }
        } else {
            cout << -1;
        }
    } else {
        cout << -1;
    }
    
    return 0;
}

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