제출 #692359

#제출 시각아이디문제언어결과실행 시간메모리
692359Farhan_HYEkoeko (COCI21_ekoeko)C++14
10 / 110
215 ms4644 KiB
#include <bits/stdc++.h> #define int long long #define float double #define pb push_back #define F first #define S second #define T int t; cin >> t; while(t--) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; /// Benzema is the best player in the world const int N = 1e6 + 6; const int M = 1e3 + 3; const int mod = 1e9 + 7; const int inf = 1e9; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int LOG = 28; int n, cnt[LOG], tree[N]; bool vis[N]; deque<int> pos[LOG]; string s; void update(int node, int tl, int tr, int idx, int val) { if (tr == tl) { tree[node] += val; return; } int mid = (tr + tl) / 2; if (idx <= mid) update(2 * node, tl, mid, idx, val); else update(2 * node + 1, mid + 1, tr, idx, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; } void update(int idx, int val) { if (idx < n) update(1, 0, n - 1, idx, val); } int get(int node, int tl, int tr, int l, int r) { if (l <= tl && tr <= r) return tree[node]; if (tr < l || tl > r) return 0; int mid = (tr + tl) / 2; int p1 = get(2 * node, tl, mid, l, r); int p2 = get(2 * node + 1, mid + 1, tr, l, r); return p1 + p2; } int get(int idx) {return get(1, 0, n - 1, 0, idx);} main() { IOS cin >> n >> s; n *= 2; for(int i = 0; i < n; i++) cnt[s[i] - 'a']++, pos[s[i] - 'a'].push_back(i); for(int i = 0; i < 26; i++) cnt[i] /= 2; string s1, s2; int ans = 0; for(int i = 0; i < n / 2; i++) { int c = -1; for(int j = 0; j < 26; j++) { if (cnt[j] == 0 || pos[j].size() == 0) continue; if (c == -1 || pos[j].front() < pos[c].front()) c = j; } cnt[c]--; vis[pos[c].front()] = 1; ans += pos[c].front() - i; pos[c].pop_front(); s1 += (c + 'a'); } for(int i = 0; i < n; i++) if (!vis[i]) s2 += s[i]; for(int i = 0; i < 26; i++) pos[i].clear(); n /= 2; for(int i = 0; i < n; i++) pos[s2[i] - 'a'].push_back(i); for(int i = 0; i < n; i++) { int idx = pos[s1[i] - 'a'].front(); idx += get(idx); ans += idx - i; pos[s1[i] - 'a'].pop_front(); update(idx, -1); int l = 0, r = i; while(l < r) { int mid = (l + r + 1) / 2; if (mid + get(mid) <= i) l = mid; else r = mid - 1; } update(r, +1); } cout << ans; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...