Submission #722276

#	Time	Username	Problem	Language	Result	Execution time	Memory
722276		gagik_2007	Boarding Passes (BOI22_passes)	C++17	30 / 100	108 ms	596 KiB

passes

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll M = 256;
const ll LG = 31;
ll n, m, k;
string s;
bool used[M];
int ind[M];

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> s;
	n = s.size();
	vector<char>p;
	int g = 0;
	for (char c : s) {
		if (!used[c]) {
			g++;
			p.push_back(c);
		}
		used[c] = true;
	}
	cout << setprecision(12) << fixed;
	if (g == 1) {
		double S = (n / 2) * (n / 2 - 1) + ((n + 1) / 2) * ((n + 1) / 2 - 1);
		cout << S / 4.0 << endl;
	}
	else if (g <= 7 && n <= 100) {
		sort(p.begin(), p.end());
		ll ans = INF;
		do {
			for (int i = 0; i < p.size(); i++) {
				ind[p[i]] = i;
			}
			ll res = 0;
			for (int i = 0; i < s.size(); i++) {
				ll fst = 0, scd = 0;
				for (int j = 0; j < i; j++) {
					if (ind[s[j]] > ind[s[i]]) {
						fst += 2;
					}
					else if (s[j] == s[i]) {
						fst += 1;
					}
				}
				for (int j = i + 1; j < s.size(); j++) {
					if (ind[s[j]] > ind[s[i]]) {
						scd += 2;
					}
					else if (s[j] == s[i]) {
						scd += 1;
					}
				}
				res += min(fst, scd);
			}
			ans = min(ans, res);
		} while (next_permutation(p.begin(), p.end()));
		cout << ld(ans) / 2.0 << endl;
	}
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:50:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |   if (!used[c]) {
      |             ^
passes.cpp:54:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |   used[c] = true;
      |        ^
passes.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for (int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~
passes.cpp:66:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |     ind[p[i]] = i;
      |             ^
passes.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for (int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
passes.cpp:72:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   72 |      if (ind[s[j]] > ind[s[i]]) {
      |                  ^
passes.cpp:72:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   72 |      if (ind[s[j]] > ind[s[i]]) {
      |                              ^
passes.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int j = i + 1; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~
passes.cpp:80:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   80 |      if (ind[s[j]] > ind[s[i]]) {
      |                  ^
passes.cpp:80:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   80 |      if (ind[s[j]] > ind[s[i]]) {
      |                              ^

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40