Submission #1098561

#TimeUsernameProblemLanguageResultExecution timeMemory
1098561NurislamJJOOII 2 (JOI20_ho_t2)C++17
0 / 100
0 ms344 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds;z #define pb push_back #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define int long long //#define ordst tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag , tree_order_statistics_node_update > //#define double long double template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int N = (1<<18) +1, inf = 1e18+200; //int mod = 998244353; //int mod = 1000000007; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng) void solve(){ map<char,int> mp; mp['J'] = 0; mp['O'] = 1; mp['I'] = 2; vector<int> a;a.pb(-1); auto conv = [&](string s)->void{ for(auto &i:s)a.pb(mp[i]); }; int n, k; cin >> n >> k; string s;cin >> s;conv(s); vector<vector<int>> pref(n+1, vector<int> (3, 0)); for(auto &i:pref[0])i = 0; for(int i = 1; i <= n; i++){ for(int j = 0; j < 3; j++) pref[i][j] = pref[i-1][j]; pref[i][a[i]]++; } auto get = [&](int l, int r, int t) -> int{ return pref[r][t] - pref[l-1][t]; }; auto ch = [&]()->bool{ vector<int> v; for(int i = 1; i <= n; i++)if(a[i] == 1)v.pb(i); for(int i = 0; i < (int)v.size(); i++){ if(i+k-1 == (int)v.size())break; int l = v[i], r = v[i+k-1]; if(get(1, l, 0) >= k && get(r, n, 2) >= k)return true; } return false; }; if(!ch()){cout << "-1\n";return;} vector<int> v; for(int i = 1; i <= n; i++)if(a[i] == 1)v.pb(i); int ans = inf; int il = 0, ir = k-1; int last = inf; while(ir < v.size()){ //cout << il << ' ' << ir << '\n'; int l = v[il]-1, r = v[ir]+1; int tol = l; for(int i = 20; i >= 0; i--){ int nwl = max(1ll, tol-(1<<i)); if(get(nwl, l, 0) >= k)continue; tol = nwl; } tol--; int tor = r; for(int i = 20; i >= 0; i--){ int nwr = min(n, tor+(1<<i)); if(get(r, nwr, 2) >= k)continue; tor = nwr; } tor++; int cur = tor-tol+1 - k*3; chmin(ans, cur); if(ir-il+1 == k)ir++; else if(ir+1 == v.size())il++; else if(chmin(last, cur))ir++; else il++; //cout << il << ' ' << ir << '\n'; } cout << ans << '\n'; } signed main(){ //ios_base::sync_with_stdio(false); //cin.tie(nullptr); //cout.tie(nullptr); int tt = 1; //cin >> tt; while(tt--){ solve(); } }

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:81:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  while(ir < v.size()){
      |        ~~~^~~~~~~~~~
ho_t2.cpp:102:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   else if(ir+1 == v.size())il++;
      |           ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...