# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1059893 | 2024-08-15T08:56:04 Z | Thanhs | Ekoeko (COCI21_ekoeko) | C++14 | 9 ms | 6036 KB |
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define endl '\n' #define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define setmin(x, y) x = min((x), (y)) #define setmax(x, y) x = max((x), (y)) #define sqr(x) ((x) * (x)) #define fi first #define se second #define all(x) x.begin(), x.end() // mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); // int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);} const int NM = 2e5 + 5; int n, bit[NM], type[NM], cnt[NM], ans; string s, ss[2]; queue<int> q[26]; void upd(int i) { for (; i <= n; i += i & -i) bit[i]++; } int get(int i) { int res = 0; for (; i; i -= i & -i) res += bit[i]; return res; } int get(int l, int r) { return get(r) - get(l - 1); } void solve() { cin >> n >> s; n = s.size(); for (char &c : s) c -= 'a'; for (int i = 0; i < n; i++) cnt[s[i]]++; for (int i = 0; i < 26; i++) cnt[i] /= 2; int t = 0; for (int i = 0; i < n; i++) { type[i] = (cnt[s[i]] ? 0 : 1); ss[type[i]] += s[i]; cnt[s[i]] = max(0ll, cnt[s[i]] - 1); if (!type[i]) ans += t; else t++; } n /= 2; for (int i = 0; i < n; i++) q[ss[0][i]].push(i + 1); for (int i = 0; i < n; i++) { int a = q[ss[1][i]].front(); q[ss[1][i]].pop(); ans += get(a, n); upd(a); } cout << ans; } signed main() { fastIO if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); } int tc = 1; // cin >> tc; while (tc--) solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 3164 KB | Output is correct |
3 | Correct | 3 ms | 5352 KB | Output is correct |
4 | Correct | 6 ms | 5864 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 3164 KB | Output is correct |
3 | Correct | 3 ms | 5352 KB | Output is correct |
4 | Correct | 6 ms | 5864 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 3164 KB | Output is correct |
3 | Correct | 3 ms | 5352 KB | Output is correct |
4 | Correct | 6 ms | 5864 KB | Output is correct |
5 | Correct | 0 ms | 2396 KB | Output is correct |
6 | Correct | 7 ms | 5888 KB | Output is correct |
7 | Correct | 7 ms | 5864 KB | Output is correct |
8 | Correct | 8 ms | 6012 KB | Output is correct |
9 | Correct | 8 ms | 5976 KB | Output is correct |
10 | Correct | 7 ms | 4072 KB | Output is correct |
11 | Correct | 8 ms | 5864 KB | Output is correct |
12 | Correct | 7 ms | 5936 KB | Output is correct |
13 | Correct | 7 ms | 5764 KB | Output is correct |
14 | Correct | 8 ms | 5928 KB | Output is correct |
15 | Correct | 7 ms | 5864 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2532 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 1 ms | 2532 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 1 ms | 2396 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 3164 KB | Output is correct |
3 | Correct | 3 ms | 5352 KB | Output is correct |
4 | Correct | 6 ms | 5864 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 7 ms | 5888 KB | Output is correct |
11 | Correct | 7 ms | 5864 KB | Output is correct |
12 | Correct | 8 ms | 6012 KB | Output is correct |
13 | Correct | 8 ms | 5976 KB | Output is correct |
14 | Correct | 7 ms | 4072 KB | Output is correct |
15 | Correct | 8 ms | 5864 KB | Output is correct |
16 | Correct | 7 ms | 5936 KB | Output is correct |
17 | Correct | 7 ms | 5764 KB | Output is correct |
18 | Correct | 8 ms | 5928 KB | Output is correct |
19 | Correct | 7 ms | 5864 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 1 ms | 2532 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
26 | Correct | 1 ms | 2532 KB | Output is correct |
27 | Correct | 1 ms | 2396 KB | Output is correct |
28 | Correct | 0 ms | 2396 KB | Output is correct |
29 | Correct | 0 ms | 2396 KB | Output is correct |
30 | Correct | 1 ms | 2396 KB | Output is correct |
31 | Correct | 1 ms | 2396 KB | Output is correct |
32 | Correct | 7 ms | 5864 KB | Output is correct |
33 | Correct | 7 ms | 6036 KB | Output is correct |
34 | Correct | 9 ms | 6008 KB | Output is correct |
35 | Correct | 7 ms | 4072 KB | Output is correct |
36 | Correct | 8 ms | 5864 KB | Output is correct |
37 | Correct | 7 ms | 5904 KB | Output is correct |
38 | Correct | 7 ms | 5960 KB | Output is correct |
39 | Correct | 7 ms | 5956 KB | Output is correct |
40 | Correct | 7 ms | 5936 KB | Output is correct |
41 | Correct | 6 ms | 5864 KB | Output is correct |