제출 #723245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723245		ducanh1234	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	55 ms	5532 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define int long long 

#define rep(i, b) for(int i = 0; i < (int)b; i++)
#define FOR(i, a, b) for(int i = a; i < (int)b; i++)
#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#define debug(a, b) cerr << "[" << #a << ", " << #b << "] = [" << a << ", " << b << "]\n";

template<class T> inline void read(T& t){ cin >> t; }
template<class T, class... H> inline void read(T& t, H&... h){ cin >> t; read(h...); }
template<class T> inline void read(vector<T>& t){ for(auto&x : t) read(x); } 
template<class T, class... H> inline void read(vector<T>& t, vector<H>&... h){ read(t); read(h...); }

template<class T> inline void wt(const T t) { cout << t; } 
template<class T> inline void write(const T t) { cout << t << " "; } 
template<class T> inline void print(const T t){ cout << t << "\n";}
template<class T, class... H> inline void wt(const T& t, const H&... h){ cout << t; wt(h...); }
template<class T, class... H> inline void print(const T& t, const H&... h){ cout << t; cout << " "; print(h...);}
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(a) (int)a.size()

bool bs(vector<int>&a, int x){
    return binary_search(all(a), x);
}
int a, b, c;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; string s; read(n, k, s);
    vector<int> pre_j(n + 1, 0), pre_o(n + 1, 0), pre_i(n + 1, 0);
    // build prefix sum
    rep(i, n){
      pre_j[i + 1] = pre_j[i] + (s[i] == 'J');
      pre_o[i + 1] = pre_o[i] + (s[i] == 'O');
      pre_i[i + 1] = pre_i[i] + (s[i] == 'I');
    }    
    int Min = 1e9, pos_j = 0, l = 0, cnt = 0, tmp = 0;
    while(true){
      if(bs(pre_j, pre_j[cnt] + k)){
        pos_j = lower_bound(all(pre_j), pre_j[cnt] + 1) - pre_j.begin();
        a = lower_bound(all(pre_j), pre_j[cnt++] + k) - pre_j.begin(); 
      }else break;
      
      if(bs(pre_o, pre_o[a] + k)){
        b = lower_bound(all(pre_o), pre_o[a] + k) - pre_o.begin();
      }else break;

      if(bs(pre_i, pre_i[b] + k)){
        c = lower_bound(all(pre_i), pre_i[b] + k) - pre_i.begin();
      }else break;
 //     print(a, pos_j, b, c);
      Min = min(Min, c - pos_j + 1 - 3 * k); 
    }
    print(Min == (int)1e9 ? -1 : Min);
    return 0;
}

/*
JOI 2020 JJOOII
- For each starting point...
    - Find the next point such that the number of "J"s between it and the starting
      point is equal to K
    - Find the next point such that the number of "O"s between it and the previous
      point is equal to K
    - Find the next point such that the number of "I"s between it and the previous
      point is equal to K
    - Notice how this is always optimal because we want to minimize the distance
      between the first and last points
- We can use 4 pointers and prefix sums to find the 4 points for each starting point
- Complexity: O(N)
*/

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

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:39:31: warning: unused variable 'l' [-Wunused-variable]
   39 |     int Min = 1e9, pos_j = 0, l = 0, cnt = 0, tmp = 0;
      |                               ^
ho_t2.cpp:39:47: warning: unused variable 'tmp' [-Wunused-variable]
   39 |     int Min = 1e9, pos_j = 0, l = 0, cnt = 0, tmp = 0;
      |                                               ^~~

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