Submission #471499

#	Time	Username	Problem	Language	Result	Execution time	Memory
471499		FatihSolak	JJOOII 2 (JOI20_ho_t2)	C++17	13 / 100	11 ms	5472 KiB

ho_t2

#include <bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
void ck(string s,int k){
    int cnt = 0;
    for(auto u:s){
        if(u == 'J' && cnt < k)cnt++;
        if(u == 'O' && cnt >= k && cnt < 2*k)cnt++;
        if(u == 'I' && cnt >= 2*k && cnt < 3*k)cnt++;
    }
    if(cnt != 3*k){
        cout << -1 << endl;
        exit(0);
    }
}
int J[N],O[N],I[N];
void solve(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    ck(s,k);
    s = "."+s;
    for(int i=0;i<N;i++){
        J[i] = O[i] = I[i] = N-1;
    }
    queue<int> J_J,O_O,I_I;
    for(int i=n;i>=1;i--){
        if(s[i] == 'J')J_J.push(i);
        if(s[i] == 'O')O_O.push(i);
        if(s[i] == 'I')I_I.push(i);
        if(J_J.size() > k)J_J.pop();
        if(O_O.size() > k)O_O.pop();
        if(I_I.size() > k)I_I.pop();
        if(J_J.size() == k)J[i] = J_J.front() + 1;
        if(O_O.size() == k)O[i] = O_O.front() + 1;
        if(I_I.size() == k)I[i] = I_I.front() + 1;
    }
    int maxi = 0;
    for(int i=1;i<=n;i++){
        maxi = max(maxi,i+n-I[O[J[i]]]);
    }
    cout << n - 3*k - maxi;

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   33 |         if(J_J.size() > k)J_J.pop();
      |            ~~~~~~~~~~~^~~
ho_t2.cpp:34:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |         if(O_O.size() > k)O_O.pop();
      |            ~~~~~~~~~~~^~~
ho_t2.cpp:35:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |         if(I_I.size() > k)I_I.pop();
      |            ~~~~~~~~~~~^~~
ho_t2.cpp:36:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   36 |         if(J_J.size() == k)J[i] = J_J.front() + 1;
      |            ~~~~~~~~~~~^~~~
ho_t2.cpp:37:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   37 |         if(O_O.size() == k)O[i] = O_O.front() + 1;
      |            ~~~~~~~~~~~^~~~
ho_t2.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |         if(I_I.size() == k)I[i] = I_I.front() + 1;
      |            ~~~~~~~~~~~^~~~

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