oj.uz

Submission #646332

# Submission time Handle Problem Language Result Execution time Memory
646332 2022-09-29T14:40:56 Z dooompy Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 659752 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int converted[100005];
int idx = 0;

long double fromleft[16][16][100005];
long double fromright[16][16][100005];
vector<vector<int>> groups;
int g;

long double calc(int amt) {
    return (long double) ((long double) amt * (long double) (amt-1.0)) / 4.0;
}

long double getans(int mask, int j, int k) {
    if (k >= groups[j].size()) return 1e15;

    long double val = calc(k + 1) + calc((int) groups[j].size() - k - 1);

    for (int i = 0; i < g; i++) {
        if ((1 << i) & mask) {
            val += fromleft[j][i][groups[j][k]];

            if (k + 1 == groups[j].size()) continue;
            val += fromright[j][i][groups[j][k+1]];
        }
    }

    return val;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);

    string s; cin >> s;
    int n = s.size();

    set<char> dup;
    map<char, int> m;

    for (int i = 0; i < n; i++) {
        if (m.count(s[i]) != 0) {
            converted[i] = m[s[i]];
        } else {
            m[s[i]] = m.size();
            converted[i] = m[s[i]];
        }
    }

    g = m.size();

    groups.resize(g);

    for (int i = 0; i < n; i++) {
        groups[converted[i]].push_back(i);
    }

    for (int l = 0; l < g; l++) {
        for (int r = 0; r < g; r++) {

            long double ct = 0, res = 0;

            for (int i = 0; i < n; i++) {
                if (converted[i] == l) {
                    ct++;
                } else if (converted[i] == r) {
                    res += ct;
                    fromleft[r][l][i] = res;
                }
            }

            ct = 0, res = 0;

            for (int i = n - 1; i >= 0 ; i--) {
                if (converted[i] == l) {
                    ct++;
                } else if (converted[i] == r) {
                    res += ct;
                    fromright[r][l][i] = res;
                }
            }
        }
    }

    vector<long double> dp(1 << g, 1e15);

    dp[0] = 0;

    for (int mask = 0; mask < (1 << g); mask++) {
        for (int j = 0; j < g; j++) {
            if (!((1 << j) & mask)) {
                long double cur = calc(groups[j].size());

                for (int i = 0; i < g; i++) {
                    if ((1 << i) & mask) {
                        cur += fromright[j][i][groups[j][0]];
                    }
                }

                for (int k = 0; k < groups[j].size(); k++) {
                    // up to k from front

                    cur = min(cur, getans(mask, j, k));
                }

                dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cur);
            }
        }
    }

    cout << setprecision(30) << fixed << dp[(1 << g) - 1];
}

Compilation message

passes.cpp: In function 'long double getans(int, int, int)':
passes.cpp:45:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     if (k >= groups[j].size()) return 1e15;
      |         ~~^~~~~~~~~~~~~~~~~~~
passes.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (k + 1 == groups[j].size()) continue;
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:132:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |                 for (int k = 0; k < groups[j].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 1428 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 1556 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 1556 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 980 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 980 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 980 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 980 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 980 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 980 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 980 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 980 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 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 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 980 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 968 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 980 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 980 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 980 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 980 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 980 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 980 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 379 ms 29908 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 219 ms 4600 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 201 ms 4628 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 233 ms 12640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 427 ms 29352 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 363 ms 29268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 369 ms 29352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 387 ms 29328 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 378 ms 29324 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 353 ms 29352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 1428 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 1556 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 1556 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 980 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 980 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 980 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 980 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 980 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 980 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 980 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 980 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 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 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 980 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 968 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 980 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 980 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 980 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 980 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 980 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 980 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 379 ms 29908 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 219 ms 4600 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 201 ms 4628 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 233 ms 12640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 427 ms 29352 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 363 ms 29268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 369 ms 29352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 387 ms 29328 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 378 ms 29324 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 353 ms 29352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 54 ms 3976 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 1556 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 1556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 1684 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 1680 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 964 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 980 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 980 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 980 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 980 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 980 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 968 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 980 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 404 ms 29908 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 209 ms 4564 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 200 ms 4620 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 214 ms 12652 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 365 ms 29356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 394 ms 29300 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 395 ms 29356 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 380 ms 29328 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 389 ms 29324 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 327 ms 29268 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2128 ms 659752 KB Time limit exceeded
97 Halted 0 ms 0 KB -