#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
int a[405], b[405], cnt[5], cntb[5];
inline int rng(int l, int r){
return uniform_int_distribution<int>(l, r)(RNG);
}
inline bool gen(int n, int st){
cntb[1] = cnt[1];
cntb[2] = cnt[2];
cntb[3] = cnt[3];
cntb[st]--;
// entr
b[0] = st;
// loop(i,1,4){
// ops(cntb[i]) spac
// } entr
int tmp = 0;
loop(i,1,n){
int choose = rng(1, 3);
tmp = 0;
while(cntb[choose] == 0 || b[i-1] == choose){
choose = (choose == 3) ? (1) : (choose + 1);
tmp++;
if(tmp >= 3) return true;
}
cntb[choose]--;
b[i] = choose;
// loop(i,1,4){
// ops(cntb[i]) spac
// } entr
}
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
freopen("in.txt", "r", stdin);
int n; string s;
cin >> n >> s;
loop(i,0,n){
if(s[i] == 'R') a[i] = 1;
else if(s[i] == 'G') a[i] = 2;
else a[i] = 3;
cnt[a[i]]++;
// b[i] = a[i];
}
int max_cnt = max(max(cnt[1], cnt[2]), cnt[3]);
int no_ans_lim;
if(n % 2 == 1){
no_ans_lim = (n + 1) / 2;
}
else{
no_ans_lim = n / 2;
}
if(max_cnt > no_ans_lim){
cout << "-1\n";
return 0;
}
int ans = n * (n - 1), tmp, start = 0;
bool can;
queue<int> Qfrom[5], Qto[5];
while((long double)clock() / CLOCKS_PER_SEC <= 0.48){
start = (start == 3) ? (1) : (start + 1);
while(cnt[start] == 0)
start = (start == 3) ? (1) : (start + 1);
if(gen(n, start)) continue;
tmp = 0;
loop(i,0,n){
if(Qto[a[i]].empty()){
Qfrom[a[i]].push(i);
}
else{
tmp += i - Qto[a[i]].front();
Qto[a[i]].pop();
}
if(Qfrom[b[i]].empty()){
Qto[b[i]].push(i);
}
else{
tmp += i - Qfrom[b[i]].front();
Qfrom[b[i]].pop();
}
}
// if(tmp < 16){
// ARR(b, n);
// op(tmp)
// loop(i,1,4) op(cntb[i])
// exit(0);
// }
ans = min(ans, tmp);
}
cout << (ans >> 1) << '\n';
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:77:10: warning: unused variable 'can' [-Wunused-variable]
77 | bool can;
| ^~~
joi2019_ho_t3.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1045 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
