| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 754042 |
2023-06-06T13:53:23 Z |
vjudge1 |
JJOOII 2 (JOI20_ho_t2) |
C++17 |
|
1 ms |
212 KB |
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define run_faster ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); ios_base::sync_with_stdio(0); cin.tie(nullptr);
using namespace std;
const double PI = 3.141592653589793;
const long long INF = 2e18;
const long long inf = 2147483647;
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// ll gcd( ll a, ll b ) {
// return b? gcd( b, a%b ): a;
// }
// ll lcm( ll a, ll b ) {
// return a/gcd( a,b ) * b;
// }
// ll bp( ll x, ll a ) {
// ll res = 1;
// while( n ) {
// if( n&1 )
// res *= a;
// a *= a;
// n >>= 1;
// }
// return res;
// }
// const int N = 1e5+1;
// vector<vector<int>> g(N);
// vector<vector<int>> r(N);
// vector<bool> used(N);
// vector<ll> comp;
// vector<ll> order;
// void dfs2( int x ) {
// used[x] = 1; // graph is directed, so
// for( int to: r[x] ) { // if || g[x].pb(y) ||,
// if( !used[to] ) { // then || r[y].pb(x) ||
// dfs2(to);
// }
// }
// comp.pb(x);
// }
// void dfs( int v ) {
// used[v] = 1;
// for( int to: g[v] ) {
// if( !used[to] ) {
// dfs(to);
// }
// }
// order.pb(v);
// }
// const int N = 1e5+1;
// vector<int> p(N);
// int get(int v) {
// return v == p[v]? v: p[v] = get(p[v]);
// }
// void unite( int a, int b ) {
// a = get(a);
// b = get(b);
// if( rand()&1 )
// swap( a,b );
// if( a!=b )
// p[a]=b;
// }
// vector<pair<ll,pair<int,int>>> g;
// vector<vector<int>> graph(N);
// vector<bool> used(N);
// void dfs( int v ) {
// used[v] = 1;
// for( int to: graph[v] ) {
// if( !used[to] ) {
// dfs(to);
// }
// }
// }
// const int N = 2e5+1;
// int parent[N], sz[N];
// void make_set( int v ) {
// parent[v] = v;
// sz[v] = 1;
// }
// int find_set( int v ) {
// if( v == parent[v] )
// return v;
// return parent[v] = find_set(parent[v]);
// }
// void union_sets( int x, int y ) {
// x = find_set( x );
// y = find_set( y );
// if( x != y ) {
// if( sz[x] < sz[y] )
// swap(x,y);
// parent[y] = x;
// sz[x]+=sz[y];
// }
// }
// const int N = 2e5+1;
// int p[N];
// int sz[N];
// int mn[N];
// int mx[N];
// int get( int v ) {
// return p[v] == v? v: p[v] = get(p[v]);
// }
// void unions( int a, int b ) {
// a = get(a);
// b = get(b);
// if( rand()&1 ) {
// swap(a,b);
// }
// if( a!=b ) {
// p[a] = b;
// sz[b]+=sz[a];
// mn[b] = min(mn[a],mn[b]);
// mx[b] = max(mx[a],mx[b]);
// }
// }
signed main()
{
// freopen( "input.in" , "r" , stdin );
// freopen( "output.out" , "w" , stdout );
run_faster;
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> pj;
vector<int> po;
vector<int> pi;
for( int i = 0; i < n; i++ ) {
if( s[i] == 'J') {
pj.pb(i);
}
}
if( pj.size() >= k ) {
for( int i = 0; i < n; i++ ) {
if( s[i] == 'O') {
po.pb(i);
}
}
if( po.size() >= k ) {
for( int i = 0; i < n; i++ ) {
if( s[i] == 'I') {
pi.pb(i);
}
}
if( pi.size() >= k ) {
ll sum = 0;
for( int i = 1; i < k; i++ ) {
sum += pi[i]-pi[i-1]-1;
}
int j = -1;
for( int i = po.size()-1; i >= 0; i-- ) {
if( po[i] < pi[0] ) {
j = i;
break;
}
}
if( j+1 >= k ) {
sum += pi[0]-po[k-1]-1;
for( int i = max(1,j+2-k); i < max(k,j); i++ ) {
sum += po[i] - po[i-1] - 1;
}
int it = -1;
for( int i = pj.size()-1; i >= 0; i-- ) {
if( pj[i] < po[0] ) {
it = i;
break;
}
}
if( it+1 >= k ) {
sum += po[max(0,j+1-k)]-pj[max(k-1,it)]-1;
for( int i = max(1,it+2-k); i < max(k,it); i++ ) {
sum += pj[i] - pj[i-1] - 1;
}
cout << sum << "\n";
for( int i: pj ) {
cout << i+1 << ' ';
}
cout << "\n";
for( int i: po ) {
cout << i+1 << ' ';
}
cout << "\n";
for( int i: pi ) {
cout << i+1 << ' ';
}
} else {
cout << -1;
}
} else {
cout << -1;
}
} else {
cout << -1;
}
} else {
cout << -1;
}
} else {
cout << -1;
}
return 0;
}
Compilation message
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:163:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
163 | if( pj.size() >= k ) {
| ~~~~~~~~~~^~~~
ho_t2.cpp:171:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
171 | if( po.size() >= k ) {
| ~~~~~~~~~~^~~~
ho_t2.cpp:179:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
179 | if( pi.size() >= k ) {
| ~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
