Submission #996780

#TimeUsernameProblemLanguageResultExecution timeMemory
996780sandrofeiqrishviliJJOOII 2 (JOI20_ho_t2)C++14
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #define int long long #define pp pop_back #define pb push_back #define eb emplace_back #define nl cout "\n" #define sp <<" " #define spc <<" "<< #define ff first #define ss second #define r0 return 0 #define INF INT_MAX #define mod 998244353 #define MOD 1000000007 #define Yes cout << "YES" << endl #define No cout << "NO" << endl #define vll vector<ll> #define vb vector<bool> #define vd vector<double> #define vs vector<string> #define pii pair <int,int> #define pll pair<ll,ll> #define pls pair<ll,string> #define psl pair<string,ll> #define plc pair<ll,char> #define pcl pair<char,ll> #define pss pair<string,string> #define pis pair<int,string> #define sz size() #define pause system("pause") #define min3(a,b,c) min(a,min(b,c)) #define all(x) (x).begin(),(x).end() #define deb(x) cout << #x << " - " << x << endl using namespace std; vector <int> vj; vector <int> vi; vector <int> vo; inline void test_case(){ int ans=INT_MAX; int n, k; cin >> n >> k; string s; cin >> s; vi.pb(-1); for(int i=0; i<n; i++){ if(s[i]=='J'){ vj.pb(i); } if(s[i]=='O'){ vo.pb(i); } if(s[i]=='I'){ vi.pb(i); } } vj.pb(INT_MAX); // cout << vj[1]; // cout << vo.size()-k+1 << endl; for(int i=0; i<vo.size()-k+1; i++){ int check=0; int l=vo[i]; int r=vo[i+k-1]; int je; int start=0; int end=vj.size()-1; while(start<end){ int mid=(start+end)/2; // deb(mid); if(vj[mid]<l && vj[mid+1]>l){ je=mid; check=1; break; } if(vj[mid+1]<l){ start=mid+1; continue; } end=mid; } // deb(check); if(check==0){ continue; } // cout << vj[je] << endl; int js=je-k+1; // cout << vj[js] << endl; check=0; int is; start=0; end=vi.size()-1; while(start<end){ int mid=(start+end)/2; // deb(mid); if(vi[mid]>r && vi[mid-1]<r){ is=mid; check=1; break; } if(vi[mid]>r){ end=mid; continue; } start=mid+1; } if(check==0){ continue; } // cout << vi[is] << endl; int ie=is+k-1; // cout << vi[ie] << endl; ans=min(ans, vi[ie]-vj[js]-3*k+1); } if(ans==INT_MAX){ cout << -1 << endl; } else{ cout << ans; } } signed main () { ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); int T = 1; // cin >> T; while(T--) { test_case(); } return 0; }

Compilation message (stderr)

ho_t2.cpp: In function 'void test_case()':
ho_t2.cpp:59:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   59 |     for(int i=0; i<vo.size()-k+1; i++){
      |                  ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...