oj.uz

Submission #722276

# Submission time Handle Problem Language Result Execution time Memory
722276 2023-04-11T16:50:05 Z gagik_2007 Boarding Passes (BOI22_passes) C++17
30 / 100
 108 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 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

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.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 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 540 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 552 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 596 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 108 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 59 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 60 ms 304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 304 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 11 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 324 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 11 ms 328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 13 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 108 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 59 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 60 ms 304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 304 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 11 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 324 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 8 ms 320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 11 ms 328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 13 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 324 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 107 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 56 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 60 ms 212 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 78 ms 300 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 320 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 9 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 10 ms 324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 8 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 9 ms 212 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 332 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Incorrect 1 ms 332 KB Unexpected end of file - double expected
38 Halted 0 ms 0 KB -

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 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 540 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 552 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 596 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 108 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 59 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 60 ms 304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 2 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 62 ms 304 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 11 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 8 ms 320 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 8 ms 324 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 9 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 8 ms 320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 11 ms 328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 7 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 8 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 13 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 324 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 107 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 56 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 60 ms 212 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 78 ms 300 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 320 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 9 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 8 ms 328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 10 ms 324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 8 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 9 ms 212 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 332 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Incorrect 1 ms 332 KB Unexpected end of file - double expected
47 Halted 0 ms 0 KB -