#include <bits/stdc++.h>
using namespace std;
// Fenwick Tree (Binary Indexed Tree) for efficient range queries and updates
struct FenwickTree {
int size;
vector<int> tree;
FenwickTree(int n) : size(n), tree(n + 1, 0) {}
// Update the tree at position idx by adding delta
void update(int idx, int delta = 1) {
while (idx <= size) {
tree[idx] += delta;
idx += idx & (-idx);
}
}
// Query the prefix sum up to and including idx
int query(int idx) const {
int res = 0;
int i = idx;
while (i > 0) {
res += tree[i];
i -= i & (-i);
}
return res;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
string C;
cin >> C;
// Count frequencies of each color
unordered_map<char, int> freq;
for(char c : C){
freq[c]++;
}
// Check feasibility
int max_freq = 0;
for(auto &[c, cnt] : freq){
if(cnt > max_freq){
max_freq = cnt;
}
}
if(max_freq > (N +1)/2){
cout << "-1";
return 0;
}
// Priority queue to build the target sequence
// Each element is a pair of (remaining_count, color)
priority_queue<pair<int, char>> pq;
for(auto &[c, cnt] : freq){
pq.emplace(cnt, c);
}
string target = "";
char prev = '#'; // Initialize with a dummy character
while(!pq.empty()){
auto [cnt, c] = pq.top(); pq.pop();
if(c == prev){
if(pq.empty()){
// Cannot rearrange to meet the condition
cout << "-1";
return 0;
}
auto [cnt2, c2] = pq.top(); pq.pop();
target += c2;
prev = c2;
if(--cnt2 >0){
pq.emplace(cnt2, c2);
}
pq.emplace(cnt, c); // Put back the previous color
}
else{
target += c;
prev = c;
if(--cnt >0){
pq.emplace(cnt, c);
}
}
}
// Now, target contains a valid rearranged sequence
// Next, compute the minimal number of adjacent swaps to convert C to target
// For each character, store the list of indices where it appears in original sequence
unordered_map<char, queue<int>> char_indices;
for(int i=0;i<N;i++){
char_indices[C[i]].push(i);
}
// Initialize Fenwick Tree
FenwickTree ft(N);
long long swaps =0;
vector<int> pos_in_original(N);
for(int i=0;i<N;i++) pos_in_original[i] = i;
for(int i=0;i<N;i++){
char current_char = target[i];
if(char_indices[current_char].empty()){
// This should not happen as we have a valid target
cout << "-1";
return 0;
}
int original_pos = char_indices[current_char].front();
char_indices[current_char].pop();
// Number of elements already moved that are before original_pos
int moved_before = ft.query(original_pos +1);
// The current position in the array after accounting for moved elements
int current_swaps = original_pos - i - moved_before;
if(current_swaps <0){
// This should not happen
cout << "-1";
return 0;
}
swaps += current_swaps;
// Mark this position as moved
ft.update(original_pos +1);
}
cout << swaps;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for(auto &[c, cnt] : freq){
| ^
joi2019_ho_t3.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto &[c, cnt] : freq){
| ^
joi2019_ho_t3.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | auto [cnt, c] = pq.top(); pq.pop();
| ^
joi2019_ho_t3.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | auto [cnt2, c2] = pq.top(); pq.pop();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
