제출 #535306

#제출 시각아이디문제언어결과실행 시간메모리
535306BiazJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
20 ms2572 KiB
#include<bits/stdc++.h> //#define int long long #define pb push_back #define ALL(x) x.begin(),x.end() #define fi first #define se second #define ist insert using namespace std; int min(int a,int b){return a<b?a:b;} int max(int a,int b){return a>b?a:b;} typedef long long ll; typedef pair<ll,ll> pii; const int N=200005; const int MOD=1000000007;//998244353 const int INF=2147483647;//1700000000000000000 int n,k; string s; vector<int> site[3]; int a[N]; vector<pii> dp[3]; bool vaild(){ int cnt=0,typ=0; for (int i=0;i<n;i++){ if (typ==0&&s[i]=='J') cnt++; if (typ==1&&s[i]=='O') cnt++; if (typ==2&&s[i]=='I') cnt++; if (cnt==k) cnt=0,typ++; } return typ==3; } int srch1(int x){ int l=0,r=dp[0].size(),res=-1; while (r>=l){ int mid=(l+r)/2; if (dp[0][mid].fi<x){ res=mid; l=mid+1; } else r=mid-1; } return res; } int srch2(int x){ int l=0,r=dp[2].size(),res=-1; while (r>=l){ int mid=(l+r)/2; if (dp[2][mid].fi>x){ res=mid; r=mid-1; } else l=mid+1; } return res; } inline void sol(){ cin >>n>>k>>s; if (!vaild()){ cout <<"-1\n"; return; } for (int i=0;i<n;i++){ if (s[i]=='J') a[i]=0; if (s[i]=='O') a[i]=1; if (s[i]=='I') a[i]=2; site[a[i]].pb(i); } int ans=INF,j=k-1; for (int t=k-1;t<site[0].size();t++){ int i=t-k+1; while (j<site[2].size()&&(lower_bound(ALL(site[1]),site[2][j-k+1])-lower_bound(ALL(site[1]),site[0][t]))<k) j++; if (j==site[2].size()) break; ans=min(ans,site[2][j]-site[0][i]+1-(k*3)); /*for (int j=k-1;j<site[2].size();j++){ if ((lower_bound(ALL(site[1]),site[2][j-k+1])-lower_bound(ALL(site[1]),site[0][t]))<k||site[0][i]>site[2][j]) continue; //cout <<site[2][j]<<' '<<site[0][i]<<'\n'; ans=min(ans,site[2][j]-site[0][i]+1-(k*3)); }*/ } cout <<ans<<'\n'; } signed main(){ int _=1; //cin >>_; while (_--) sol(); return 0; }

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

ho_t2.cpp: In function 'void sol()':
ho_t2.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int t=k-1;t<site[0].size();t++){
      |                    ~^~~~~~~~~~~~~~~
ho_t2.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while (j<site[2].size()&&(lower_bound(ALL(site[1]),site[2][j-k+1])-lower_bound(ALL(site[1]),site[0][t]))<k) j++;
      |                ~^~~~~~~~~~~~~~~
ho_t2.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if (j==site[2].size()) break;
      |             ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...