# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
647123 | 2022-10-01T16:16:20 Z | Alma | Ekoeko (COCI21_ekoeko) | C++14 | 2 ms | 340 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second using ll = long long; using ii = pair<int,int>; const int INF = 1e9; const ll LLINF = 1e18; using vi = vector<int>; using vvi = vector<vi>; void setIO (string fileName) { ios::sync_with_stdio(false); cin.tie(NULL); if (fileName != "std") { freopen((fileName + ".in").c_str(), "r", stdin); freopen((fileName + ".out").c_str(), "w", stdout); } } int n; vi bit; void update (int i, int val) { for (; i <= n; i += i&-i) { bit[i] += val; } } int query (int i) { int sum = 0; for (; i > 0; i -= i&-i) { sum += bit[i]; } return sum; } int main() { setIO("std"); cin >> n; n *= 2; string s; cin >> s; vi a(n), b, c; for (int i = 0; i < n; i++) { a[i] = s[i] - 'a'; } c = a; sort(c.begin(), c.end()); vi frec(26, 0); for (int i = 0; i < n; i += 2) { frec[c[i]]++; } for (int i = 0; i < n; i++) { if (frec[a[i]] > 0) { b.push_back(a[i]); frec[a[i]]--; } } vvi pos(26); for (int i = 0; i < n/2; i++) { b.push_back(b[i]); pos[b[i]].push_back(i); pos[b[i]].push_back(n/2 + i); } // turn a into b // obtain permutation -> count inversions vi perm(n); for (int i = 0; i < n; i++) { int dist = 1e6; int idx = 0; for (int j = 0; j < (int)pos[a[i]].size(); j++) { if (pos[a[i]][j] == -1) continue; if (abs(i - pos[a[i]][j]) < dist) { dist = abs(i - pos[a[i]][j]); idx = pos[a[i]][j]; } } perm[i] = idx+1; for (int j = 0; j < (int)pos[a[i]].size(); j++) { if (pos[a[i]][j] == -1) continue; if (abs(i - pos[a[i]][j]) == dist) { pos[a[i]][j] = -1; } } } // for (int i = 0; i < n; i++) { // cout << perm[i] << ' '; // } cout << '\n'; int ans = 0; bit = vi(n+1, 0); for (int i = n-1; i >= 0; i--) { ans += query(perm[i]-1); update(perm[i], 1); } cout << ans << '\n'; return 0; }
Compilation message
# | 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 | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Incorrect | 2 ms | 340 KB | Output isn't correct |
3 | 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 | - |