oj.uz

답안 #996780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
996780 2024-06-11T08:06:20 Z sandrofeiqrishvili JJOOII 2 (JOI20_ho_t2) C++14
0 / 100
 0 ms 348 KB 
#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

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++){
      |                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -