Submission #923924

# Submission time Handle Problem Language Result Execution time Memory
923924 2024-02-08T06:41:12 Z yeediot JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
12 ms 3376 KB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s=' '+s;
    vector<vector<int>>pos(3);
    for(int i=1;i<=n;i++){
        if(s[i]=='J')pos[0].pb(200000-i);
        else if(s[i]=='O')pos[1].pb(i);
        else if(s[i]=='I')pos[2].pb(i);
    }
    reverse(all(pos[0]));
    int ans=8e18;
    //for(auto i:pos[0])cout<<i<<' ';
    //cout<<'\n';
    for(int i=0;i+k<=sz(pos[1]);i++){
        int l=pos[1][i];
        int r=pos[1][i+k-1];
        int temp=r-l+1-k;
        l=200000-l;
        //cout<<temp<<' ';
        int x=lower_bound(all(pos[0]),l)-pos[0].begin();
        if(x+k>sz(pos[0]))continue;
        int y=lower_bound(all(pos[2]),r)-pos[2].begin();
        if(y+k>sz(pos[2]))continue;
        //cout<<pos[0][x+k-1]<<' '<<l<<' ';
        temp+=pos[0][x+k-1]-l-k+pos[2][y+k-1]-r-k;
        ans=min(ans,temp);
    }
    if(ans==8e18){
        cout<<-1<<'\n';
    }
    else{
        cout<<ans<<'\n';
    }
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 600 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 600 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 8 ms 2600 KB Output is correct
37 Correct 11 ms 2848 KB Output is correct
38 Correct 12 ms 2944 KB Output is correct
39 Correct 9 ms 2960 KB Output is correct
40 Correct 8 ms 2968 KB Output is correct
41 Correct 8 ms 3356 KB Output is correct
42 Correct 9 ms 2880 KB Output is correct
43 Correct 4 ms 1872 KB Output is correct
44 Correct 7 ms 2372 KB Output is correct
45 Correct 7 ms 3352 KB Output is correct
46 Correct 6 ms 3376 KB Output is correct
47 Correct 7 ms 3352 KB Output is correct
48 Correct 7 ms 3352 KB Output is correct
49 Correct 4 ms 2140 KB Output is correct
50 Correct 7 ms 3356 KB Output is correct
51 Correct 6 ms 2844 KB Output is correct
52 Correct 4 ms 2852 KB Output is correct
53 Correct 4 ms 2844 KB Output is correct
54 Correct 5 ms 3228 KB Output is correct
55 Correct 3 ms 3228 KB Output is correct
56 Correct 3 ms 3232 KB Output is correct