Submission #754042

#	Time	Username	Problem	Language	Result	Execution time	Memory
754042		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	212 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;
    
    vector<int> pj;
    vector<int> po;
    vector<int> pi;
    
    for( int i = 0; i < n; i++ ) {
        if( s[i] == 'J') {
            pj.pb(i);
        }
    }
    
    if( pj.size() >= k ) {
        
        for( int i = 0; i < n; i++ ) {
            if( s[i] == 'O') {
                po.pb(i);
            }
        }
        
        if( po.size() >= k ) {
        
            for( int i = 0; i < n; i++ ) {
                if( s[i] == 'I') {
                    pi.pb(i);
                }
            }
        
            if( pi.size() >= k ) {
        
                ll sum = 0;
                for( int i = 1; i < k; i++ ) {
                    sum += pi[i]-pi[i-1]-1;
                }
                int j = -1;
                for( int i = po.size()-1; i >= 0; i-- ) {
                    if( po[i] < pi[0] ) {
                        j = i;
                        break;
                    }
                }
                if( j+1 >= k ) {
                    
                    sum += pi[0]-po[k-1]-1;
                    
                    for( int i = max(1,j+2-k); i < max(k,j); i++ ) {
                        sum += po[i] - po[i-1] - 1;
                    }
                    int it = -1;
                    for( int i = pj.size()-1; i >= 0; i-- ) {
                        if( pj[i] < po[0] ) {
                            it = i;
                            break;
                        }
                    }
                    if( it+1 >= k ) {
                        
                        sum += po[max(0,j+1-k)]-pj[max(k-1,it)]-1;
                        for( int i = max(1,it+2-k); i < max(k,it); i++ ) {
                            sum += pj[i] - pj[i-1] - 1;
                        }
                        cout << sum << "\n";
                        for( int i: pj ) {
                            cout << i+1 << ' ';
                        }
                        cout << "\n";
                        for( int i: po ) {
                            cout << i+1 << ' ';
                        }
                        cout << "\n";
                        for( int i: pi ) {
                            cout << i+1 << ' ';
                        }
                        
                    } else {
                        cout << -1;
                    }
                } else {
                    cout << -1;
                }
            } else {
                cout << -1;
            }
        } else {
            cout << -1;
        }
    } else {
        cout << -1;
    }
    
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:163:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  163 |     if( pj.size() >= k ) {
      |         ~~~~~~~~~~^~~~
ho_t2.cpp:171:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |         if( po.size() >= k ) {
      |             ~~~~~~~~~~^~~~
ho_t2.cpp:179:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  179 |             if( pi.size() >= k ) {
      |                 ~~~~~~~~~~^~~~

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