Submission #722310

#	Time	Username	Problem	Language	Result	Execution time	Memory
722310		gagik_2007	Boarding Passes (BOI22_passes)	C++17	60 / 100	195 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 SZ = (1 << 10) + 7;
const ll LG = 31;
ll n, m, k;
string s;
bool used[M];
int ind[M];
ll dp[SZ];
ll pf[N];

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;
	}
	else if (g <= 10 && n <= 10000) {
		sort(p.begin(), p.end());
		for (int i = 0; i < p.size(); i++) {
			ind[p[i]] = i;
		}
		for (int msk = 1; msk < (1 << g); msk++) {
			dp[msk] = INF;
			for (int i = 0; i < g; i++) {
				if (msk & (1 << i)) {
					ll full = 0;
					for (int j = 0; j < n; j++) {
						if (ind[s[j]] == i) {
							full++;
						}
						else if (msk & (1 << (ind[s[j]]))) {
							full += 2;
						}
					}
					ll cur = 0;
					ll res = 0;
					for (int j = 0; j < n; j++) {
						ll tmp = cur;
						if (ind[s[j]] == i) {
							cur++;
						}
						else if (msk & (1 << (ind[s[j]]))) {
							cur += 2;
						}
						if (ind[s[j]] == i) res += min(tmp, full - cur);
					}
					dp[msk] = min(dp[msk], dp[msk ^ (1 << i)] + res);
				}
			}
			//cout << dp[msk] << " ";
		}
		cout << ld(dp[(1 << g) - 1]) / 2.0 << endl;
	}
}

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

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:53:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |   if (!used[c]) {
      |             ^
passes.cpp:57:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |   used[c] = true;
      |        ^
passes.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for (int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~
passes.cpp:69:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |     ind[p[i]] = i;
      |             ^
passes.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for (int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
passes.cpp:75:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |      if (ind[s[j]] > ind[s[i]]) {
      |                  ^
passes.cpp:75:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |      if (ind[s[j]] > ind[s[i]]) {
      |                              ^
passes.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int j = i + 1; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~
passes.cpp:83:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |      if (ind[s[j]] > ind[s[i]]) {
      |                  ^
passes.cpp:83:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |      if (ind[s[j]] > ind[s[i]]) {
      |                              ^
passes.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for (int i = 0; i < p.size(); i++) {
      |                   ~~^~~~~~~~~~
passes.cpp:99:12: warning: array subscript has type 'char' [-Wchar-subscripts]
   99 |    ind[p[i]] = i;
      |            ^
passes.cpp:107:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  107 |       if (ind[s[j]] == i) {
      |                   ^
passes.cpp:110:37: warning: array subscript has type 'char' [-Wchar-subscripts]
  110 |       else if (msk & (1 << (ind[s[j]]))) {
      |                                     ^
passes.cpp:118:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |       if (ind[s[j]] == i) {
      |                   ^
passes.cpp:121:37: warning: array subscript has type 'char' [-Wchar-subscripts]
  121 |       else if (msk & (1 << (ind[s[j]]))) {
      |                                     ^
passes.cpp:124:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  124 |       if (ind[s[j]] == i) res += min(tmp, full - cur);
      |                   ^

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