oj.uz

Submission #722310

# Submission time Handle Problem Language Result Execution time Memory
722310 2023-04-11T18:06:41 Z gagik_2007 Boarding Passes (BOI22_passes) C++17
60 / 100
 195 ms 596 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 596 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 596 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 592 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 85 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 50 ms 308 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 58 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 324 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 50 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 332 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 85 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 50 ms 308 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 58 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 324 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 50 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 332 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 87 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 51 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 57 ms 308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 50 ms 312 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 8 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 8 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 8 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 9 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 9 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 8 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 8 ms 256 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 195 ms 340 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 98 ms 348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 98 ms 340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 99 ms 348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 118 ms 340 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 116 ms 340 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 123 ms 348 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 123 ms 348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 125 ms 348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 118 ms 364 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 596 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 596 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 592 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 85 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 50 ms 308 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 58 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 2 ms 324 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 50 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 8 ms 328 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 8 ms 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 8 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 8 ms 328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 9 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 7 ms 332 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 7 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 8 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 87 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 51 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 57 ms 308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 2 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 50 ms 312 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 2 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 8 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 8 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 8 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 9 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 9 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 7 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 8 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 8 ms 256 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 195 ms 340 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 98 ms 348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 98 ms 340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 99 ms 348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 118 ms 340 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 116 ms 340 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 123 ms 348 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 123 ms 348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 125 ms 348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 118 ms 364 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 0 ms 212 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Incorrect 1 ms 212 KB Unexpected end of file - double expected
58 Halted 0 ms 0 KB -