답안 #529390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529390 2022-02-23T00:38:08 Z penguinhacker Ekoeko (COCI21_ekoeko) C++14
110 / 110
10 ms 2744 KB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, cnt[26], p[mxN], ft[mxN+1];
string s, a, b;
ll ans;
vector<int> oc1[26], oc2[26];

void upd(int i) {
	for (++i; i<=n; i+=i&-i)
		++ft[i];
}

int qry(int i) {
	int r=0;
	for (++i; i; i-=i&-i)
		r+=ft[i];
	return r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for (char c : s)
		++cnt[c-'a'];
	for (int i=0; i<26; ++i)
		cnt[i]/=2;
	for (int i=0, x=0; i<2*n; ++i) {
		if (cnt[s[i]-'a'])
			a+=s[i], ans+=x, --cnt[s[i]-'a'];
		else
			b+=s[i], ++x;
	}
	for (int i=0; i<n; ++i) {
		oc1[a[i]-'a'].push_back(i);
		oc2[b[i]-'a'].push_back(i);
	}
	for (int i=0; i<26; ++i)
		for (int j=0; j<oc1[i].size(); ++j)
			p[oc2[i][j]]=oc1[i][j];
	for (int i=0; i<n; ++i) {
		ans+=i-qry(p[i]);
		upd(p[i]);
	}
	cout << ans;
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j=0; j<oc1[i].size(); ++j)
      |                 ~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1220 KB Output is correct
3 Correct 6 ms 2060 KB Output is correct
4 Correct 8 ms 2744 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1220 KB Output is correct
3 Correct 6 ms 2060 KB Output is correct
4 Correct 8 ms 2744 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1220 KB Output is correct
3 Correct 6 ms 2060 KB Output is correct
4 Correct 8 ms 2744 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 10 ms 2636 KB Output is correct
7 Correct 9 ms 2648 KB Output is correct
8 Correct 8 ms 2648 KB Output is correct
9 Correct 9 ms 2620 KB Output is correct
10 Correct 8 ms 2520 KB Output is correct
11 Correct 8 ms 2488 KB Output is correct
12 Correct 8 ms 2492 KB Output is correct
13 Correct 8 ms 2500 KB Output is correct
14 Correct 8 ms 2520 KB Output is correct
15 Correct 8 ms 2520 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1220 KB Output is correct
3 Correct 6 ms 2060 KB Output is correct
4 Correct 8 ms 2744 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 10 ms 2636 KB Output is correct
11 Correct 9 ms 2648 KB Output is correct
12 Correct 8 ms 2648 KB Output is correct
13 Correct 9 ms 2620 KB Output is correct
14 Correct 8 ms 2520 KB Output is correct
15 Correct 8 ms 2488 KB Output is correct
16 Correct 8 ms 2492 KB Output is correct
17 Correct 8 ms 2500 KB Output is correct
18 Correct 8 ms 2520 KB Output is correct
19 Correct 8 ms 2520 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 0 ms 332 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 9 ms 2516 KB Output is correct
33 Correct 9 ms 2648 KB Output is correct
34 Correct 9 ms 2648 KB Output is correct
35 Correct 8 ms 2520 KB Output is correct
36 Correct 8 ms 2648 KB Output is correct
37 Correct 8 ms 2596 KB Output is correct
38 Correct 8 ms 2588 KB Output is correct
39 Correct 8 ms 2520 KB Output is correct
40 Correct 8 ms 2520 KB Output is correct
41 Correct 8 ms 2484 KB Output is correct