Submission #246937

#TimeUsernameProblemLanguageResultExecution timeMemory
246937xiryssJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
15 ms2180 KiB
//#pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math") /*#pragma GCC optimize("section-anchors") #pragma GCC optimize("profile-values,profile-reorder-functions,tracer") #pragma GCC optimize("vpt") #pragma GCC optimize("rename-registers") #pragma GCC optimize("move-loop-invariants") #pragma GCC optimize("unswitch-loops") #pragma GCC optimize("function-sections") #pragma GCC optimize("data-sections") #pragma GCC optimize("branch-target-load-optimize") #pragma GCC optimize("branch-target-load-optimize2") #pragma GCC optimize("btr-bb-exclusive")*/ //#pragma comment(linker, "/STACK:367077216") #define _CRT_SECURE_NO_WARNINGS #include <chrono> #include <set> #include <map> #include <deque> #include <string> #include <cstdint> #include <cmath> #include <queue> #include <cassert> #include <random> #include <bitset> #include <iomanip> #include <numeric> #include <time.h>////////////// #include <ctime> #include <string> #include <cstdio> #include <vector> #include <cstdlib> #include <iostream> #include <algorithm> #include <unordered_map> #include <unordered_set> //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ //#define endl '\n' #define mp make_pair #define pbc push_back #define pob pop_back() #define empb emplace_back #define queuel queue<long long> #define sqr(a) ((a) * (a)) #define sqrl(a) (ll(a)*ll(a)) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pin(p) cin >> p.first >> p.second; #define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin()); #define rev(v) reverse(v.begin(), v.end()); #define sout(s, c) for (auto i : s) cout << i << c; #define pout(p) cout << p.first << " " << p.second; #define er(v, l, r) erase(v.begin() + l, v.begin() + r); #define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i]; #define vout(v, c) for (int i = 0; i < v.size(); ++i) cout << v[i] << c; #define pushi(v, a) for (int i = 0; i < a.size(); ++i) v.push_back(a[i]); #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); srand(time(NULL)) #define dab(v) for(auto i:v)cout<<i<<' '; #define sp system("pause") //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ using namespace std; //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ typedef long long ll; typedef long double ld; typedef unsigned long long ull; //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ mt19937 rnd(time(0) + 228 + 'k' + 'e' + 'k' + 'e' + 'r' + 'o' + 'f' + 'e' + 'y'); const ld EPS = 1e-5;//(cos,-sin), (sin, cos) bool checkprime(int x) { for (int i = 2; i * i <= x; ++i) if (x % i == 0) return 0; return 1; } const ld PI = acos(-1); const int MOD7 = 1000000007; const int MOD9 = 1000000009; const ll INF = 1e18; int mod = MOD9; const int inf = 1e9; const int MAXN = 5e4 + 2; signed main() { fastio(); int n, k; cin >> n >> k; string s; cin >> s; vector<int> poso; vector<int> posj; vector<int> posi; for (int i = 0; i < n; ++i) { if (s[i] == 'O') poso.pbc(i); else if (s[i] == 'I') posi.pbc(i); else posj.pbc(i); } int ans = inf; for (int i = 0; i + k-1 < poso.size(); ++i) { int tpos = poso[i + k - 1]; int tans = tpos - poso[i] - (k - 1); int lul = lower_bound(all(posi), tpos) - posi.begin(); if (lul + k - 1 >= posi.size()) continue; tans += posi[lul] - tpos - 1; tans += posi[lul + k - 1] - posi[lul] - (k - 1); int j = lower_bound(all(posj), poso[i]) - posj.begin(); if (j == 0) continue; j--; if (j < k - 1) continue; tans += poso[i] - posj[j] - 1; tans += posj[j] - posj[j - k + 1] - (k - 1); ans = min(ans, tans); } cout << (ans == inf ?-1 : ans); sp; }

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:103:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + k-1 < poso.size(); ++i)
                  ~~~~~~~~^~~~~~~~~~~~~
ho_t2.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (lul + k - 1 >= posi.size()) continue;
       ~~~~~~~~~~~~^~~~~~~~~~~~~~
ho_t2.cpp:63:18: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
 #define sp system("pause")
            ~~~~~~^~~~~~~~~
ho_t2.cpp:120:2: note: in expansion of macro 'sp'
  sp;
  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...