제출 #509620

#제출 시각아이디문제언어결과실행 시간메모리
509620KhizriJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
9 ms3932 KiB
#include <bits/stdc++.h> using namespace std; //------------------------------DEFINE------------------------------ //****************************************************************** #define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0) #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) #define endl "\n" //****************************************************************** //----------------------------FUNCTION------------------------------ //****************************************************************** ll gcd(ll a,ll b){ if(a>b) swap(a,b); if(a==0) return a+b; return gcd(b%a,a); } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } bool is_prime(ll n){ ll k=sqrt(n); if(n==2) return true; if(n<2||n%2==0||k*k==n) return false; for(int i=3;i<=k;i+=2){ if(n%i==0){ return false; } } return true; } //***************************************************************** //--------------------------MAIN-CODE------------------------------ const int mxn=2e5+5; int t=1,n,k,pref[mxn][4]; string s; int f(char c){ if(c=='J') return 0; if(c=='O') return 1; return 2; } void solve(){ cin>>n>>k>>s; int a=-1,b=-1,x=-1,y=-1,l=-1,r=-1,ans=1e6,say=0; pref[0][f(s[0])]=1; for(int i=1;i<s.size();i++){ pref[i][0]=pref[i-1][0]; pref[i][1]=pref[i-1][1]; pref[i][2]=pref[i-1][2]; pref[i][f(s[i])]=pref[i-1][f(s[i])]+1; } for(int i=0;i<n&&say<k;i++){ if(s[i]=='J'){ say++; if(a==-1){ a=i; } if(say==k){ b=i; break; } } } if(say<k){ cout<<-1<<endl; return; } say=0; for(int i=b+1;i<n&&say<k;i++){ if(s[i]=='O'){ say++; if(x==-1){ x=i; } if(say==k){ y=i; break; } } } if(say<k){ cout<<-1<<endl; return; } say=0; for(int i=y+1;i<n&&say<k;i++){ if(s[i]=='I'){ say++; if(l==-1){ l=i; } if(say==k){ r=i; break; } } } if(say<k){ cout<<-1<<endl; return; } ans=min(ans,r-a+1-k*3); while(true){ do{ a++; }while(s[a]!='J'&&a<n); if(a==n) break; b=max(b,a); bool q=true; for(int i=b;i<n;i++){ if(pref[i][0]-pref[a-1][0]>=k){ b=i; q=false; break; } } if(q){ break; } x=max(b+1,x); y=max(x,y); q=true; for(int i=y;i<n;i++){ if(pref[i][1]-pref[x-1][1]>=k){ y=i; q=false; break; } } if(q){ break; } l=max(l,y+1); r=max(r,l); q=true; for(int i=r;i<n;i++){ if(pref[i][2]-pref[l-1][2]>=k){ r=i; q=false; break; } } if(q){ break; } ans=min(ans,r-a+1-k*3); } if(ans==1e6){ cout<<-1<<endl; return; } cout<<ans<<endl; } int main(){ IOS; //cin>>t; while(t--){ solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=1;i<s.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...