이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
string s;
cin >> s;
int n = s.size();
int a[n], maxx = 0;
map<int, int> cc;
for(int i = 0; i < n; i++)
{
a[i] = s[i] - 'A';
cc[a[i]] = 1;
}
int cnt = 0;
for(auto i: cc)
{
cc[i.first] = cnt++;
}
for(int i = 0; i < n; i++)
{
a[i] = cc[a[i]];
maxx = max(maxx, a[i]);
}
vector<int> perm;
double ans = 1e18;
for(int i = 0; i <= maxx; i++)
{
perm.push_back(i);
}
do
{
vector<bool> visited(n, false);
double final_ans = 0.0;
// cout << "----------------------------\n";
// cout << perm[0] << " " << perm[1] << " " << perm[2] << " " << perm[3] << " " << perm[4] << "\n";
for(int cur_idx = 0; cur_idx < perm.size(); cur_idx++)
{
// cout << "cur_idx = " << cur_idx << "\n";
vector<int> indices;
for(int j = 0; j < n; j++)
{
if(perm[cur_idx] == a[j])
{
indices.push_back(j);
}
}
int siz = indices.size();
vector<int> prefix_impact(siz, 0), suffix_impact(siz, 0);
int cnt = 0, pos = 0;
for(int i = 0; i < n; i++)
{
if(visited[i])
{
cnt++;
}
if(pos != siz && i == indices[pos])
{
pos++;
prefix_impact[pos - 1] = cnt;
}
}
// cout << "prefix_impact\n";
// for(int i = 0; i < siz; i++)
// {
// cout << prefix_impact[i] << " ";
// }
// cout << "\n";
// cout << "suffix_impact\n";
// for(int i = 0; i < siz; i++)
// {
// cout << suffix_impact[i] << " ";
// }
// cout << "\n";
cnt = 0;
pos = siz - 1;
int current_independent = 0;
for(int i = n - 1; i >= 0; i--)
{
if(visited[i])
{
cnt++;
}
if(pos != -1 && i == indices[pos])
{
pos--;
suffix_impact[pos + 1] = cnt;
current_independent += cnt;
}
}
double cur_ans = current_independent;
double siz_d = siz;
cur_ans = (cur_ans + (siz_d * (siz_d - 1)) / 4);
// cout << "a1 = " << 0 << ", a2 = " << siz_d << ", cur_ans = " << cur_ans << ", not depend = " << current_independent << "\n";
double holy_ans = cur_ans;
// cout << "cur_ans = " << cur_ans << "\n";
for(int x = 0; x < indices.size(); x++)
{
cur_ans = 0;
current_independent = current_independent - suffix_impact[x] + prefix_impact[x];
cur_ans = current_independent;
// cout << "current_independent = " << current_independent << "\n";
int y = indices.size();
double a1 = x + 1;
double a2 = y - a1;
cur_ans = cur_ans + (a1 * (a1 - 1)) / 4.00;
if(a2 != 0)
{
cur_ans = cur_ans + (a2 * (a2 - 1)) / 4.00;
}
// cout << "a1 = " << a1 << ", a2 = " << a2 << ", cur_ans = " << cur_ans << ", not depend = " << current_independent << "\n";
holy_ans = min(holy_ans, cur_ans);
}
// cout << "finally adding: " << holy_ans << "\n";
final_ans += holy_ans;
for(int i = 0; i < siz; i++)
{
// cout << "indices[i] = " << indices[i] << "\n";
visited[indices[i]] = true;
}
}
// cout << "final_ans = " << final_ans << "\n";
// cout << perm[0] << " " << perm[1] << " " << perm[2] << " " << perm[3] << " " << perm[4] << "\n";
// cout << "----------------------------\n";
ans = min(ans, final_ans);
} while(next_permutation(perm.begin(), perm.end()));
cout << fixed << setprecision(10) << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
passes.cpp: In function 'void Solve()':
passes.cpp:42:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int cur_idx = 0; cur_idx < perm.size(); cur_idx++)
| ~~~~~~~~^~~~~~~~~~~~~
passes.cpp:102:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int x = 0; x < indices.size(); x++)
| ~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |