#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N;
string S;
int inv(vector<int> v) {
int res = 0;
bool sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < v.size()-1; i++) {
if (v[i] > v[i+1]) {
swap(v[i],v[i+1]);
res++;
sorted = false;
}
}
}
return res;
}
int main() {
cin >> N >> S;
int cR = count(S.begin(),S.end(),'R'), cG = N-cR;
if (abs(cG-cR) <= 1) {
int distM = INF;
if (cG >= cR) {
int curR = 1, curG = 0;
vector<int> v(N);
for (int i = 0; i < N; i++) {
if (S[i] == 'R') {
v[i] = curR;
curR += 2;
}
else if (S[i] == 'G') {
v[i] = curG;
curG += 2;
}
}
distM = min(distM,inv(v));
}
if (cR >= cG) {
int curR = 0, curG = 1;
vector<int> v(N);
for (int i = 0; i < N; i++) {
if (S[i] == 'R') {
v[i] = curR;
curR += 2;
}
else if (S[i] == 'G') {
v[i] = curG;
curG += 2;
}
}
distM = min(distM,inv(v));
}
cout << distM << "\n";
}
else {
cout << "-1\n";
}
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int inv(std::vector<int>)':
joi2019_ho_t3.cpp:15:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size()-1; i++) {
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |