Submission #201571

#	Time	Username	Problem	Language	Result	Execution time	Memory
201571		theStaticMind	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	23 ms	5240 KiB

ho_t2

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
int lower(vector<int>& arr, int x){
      int l = 0;
      int r = (int)arr.size() - 1;
      int ret = -1;
      while(l <= r){
            int mid = (l + r) / 2;
            if(arr[mid] >= x){
                  r = mid - 1;
                  ret = mid;
            }
            else l = mid + 1;
      }
      return ret;
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
//      freopen("q.gir","r",stdin);
//      freopen("q.cik","w",stdout);
      int n, k, ans = INF;
      cin >> n >> k;
      string s;
      cin >> s;
      vector<int> arr(1, -1);
      vector<int> data[3];
      for(int i = 0; i < n; i++){
            if(s[i] == 'J')arr.pb(0);
            if(s[i] == 'O')arr.pb(1);
            if(s[i] == 'I')arr.pb(2);
      }
      for(int i = 1; i <= n; i++){
            data[arr[i]].pb(i);
      }
      for(int i = 0; i + k - 1 < data[0].size(); i++){
            int sj = i;
            int ej = i + k - 1;
            int so = lower(data[1], data[0][ej]);
            if(so == -1 || so + k - 1 >= data[1].size())continue;
            int eo = so + k - 1;
            int si = lower(data[2], data[1][eo]);
            if(si == -1 || si + k - 1 >= data[2].size())continue;
            int ei = si + k - 1;
            ans = min(ans, data[2][ei] - data[0][i] + 1 - 3 * k);
      }
      if(ans == INF)cout << -1;
      else cout << ans;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int32_t main()':
ho_t2.cpp:43:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i + k - 1 < data[0].size(); i++){
                      ~~~~~~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:47:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(so == -1 || so + k - 1 >= data[1].size())continue;
                            ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:50:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(si == -1 || si + k - 1 >= data[2].size())continue;
                            ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:44:17: warning: unused variable 'sj' [-Wunused-variable]
             int sj = i;
                 ^~

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