Submission #680626

#	Time	Username	Problem	Language	Result	Execution time	Memory
680626		vinnipuh01	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	0 ms	340 KiB

ho_t2

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int p[ 200001 ], sf[ 200001 ], mp[ 200001 ];
int pp[ 200001 ], sff[ 200001 ], mpp[ 200001 ];

main () {
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	while ( s.size() && s.back() != 'I' )
		s.pop_back();
	reverse( s.begin(), s.end() );
	while ( s.size() && s.back() != 'J' )
		s.pop_back();
	reverse( s.begin(), s.end() );
	for ( int i = 0; i < s.size(); i ++ ) {
		if ( i )
			p[ i ] = p[ i - 1 ], sf[ i ] = sf[ i - 1 ], mp[ i ] = mp[ i - 1 ], pp[ i ] = pp[ i - 1 ], mpp[ i ] = mpp[ i - 1 ], sff[ i ] = sff[ i - 1 ];
		if ( s[ i ] == 'J' ) {
			p[ i ] ++;
			pp[  i] = i;
		}
		else if ( s[ i ] == 'O' )
			sf[ i ] ++, sff[ i ] = i;
		else
			mp[ i ] ++, mpp[ i ] = i;
	} 
	int l, r, mid;
	ans = oo;
	for ( int i = 0; i < s.size(); i ++ ) {
		if ( s[ i ] != 'J' || p[ i ] < m )
			continue;
		l = 0;
		r = i;
		sum = 0;
		while ( r - l > 1 ) {
			mid = ( l + r ) / 2;
			if ( p[ i ] - p[ mid ] + 1 >= m )
				l = mid;
			else
				r = mid - 1;
		}
		if ( p[ i ] - p[ l ] + 1 < m )
			continue;
		if ( p[ i ] - p[ r ] + 1 >= m )
			l = r;
		l = pp[ l ];
		sum += i - l + 1 - m;
		l = i;
		r = s.size() - 1;
		while ( r > l ) {
			mid = ( l + r ) / 2;
			if ( sf[ mid ] - sf[ i ] >= m )
				r = mid;
			else
				l = mid + 1;
		}
		if ( sf[ l ] - sf[ i ] < m )
			continue;
		l = sff[ l ];
		sum += l - i - m;
		pos = l + 1;
		l = pos;
		r = s.size() - 1;
		while ( r > l ) {
			mid = ( l + r ) / 2;
			if ( mp[ mid ] - mp[ pos ] + 1 >= m )
				r = mid;
			else
				l = mid + 1; 
		}
		if ( mp[ l ] - mp[ pos ] + 1 < m )
			continue;
		l = mpp[ l ];
		sum += l - pos + 1 - m;
		ans = min( ans, sum );
	}
	if ( ans == oo )
		cout << "-1";
	else
		cout << ans;
}

Compilation message (stderr)

ho_t2.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main () {
      | ^~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:61:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for ( int i = 0; i < s.size(); i ++ ) {
      |                   ~~^~~~~~~~~~
ho_t2.cpp:75:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for ( int i = 0; i < s.size(); i ++ ) {
      |                   ~~^~~~~~~~~~

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