oj.uz

Submission #646331

# Submission time Handle Problem Language Result Execution time Memory
646331 2022-09-29T14:39:48 Z dooompy Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 659888 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 k = 0; k < g; k++) {
                    if (mask & (1 << k)) {
                        cur += fromright[j][k][groups[j][0]];
                    }
                }

                for (int k = 0; k < groups[j].size(); k++) {
                    long double val = calc(k + 1) + calc((int)(groups[j].size()) - k - 1);
                    for (int l = 0; l < g; l++) {
                        if (mask & (1 << l)) {
                            val += fromleft[j][l][groups[j][k]];
                            if (k + 1 < groups[j].size()) {
                                val += fromright[j][l][groups[j][k + 1]];
                            }
                        }
                    }
                    cur = min(cur, val);
                }

                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++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~
passes.cpp:137:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                             if (k + 1 < groups[j].size()) {
      |                                 ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 1 ms 340 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 3 ms 1556 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 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 1 ms 340 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 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 980 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 2 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 968 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 1 ms 340 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 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 980 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 2 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 968 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 332 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 328 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 1024 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 968 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 964 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 980 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 960 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 1016 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 512 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 422 ms 29896 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 204 ms 4600 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 220 ms 4624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 180 ms 12660 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 418 ms 29344 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 324 ms 29268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 348 ms 29352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 431 ms 29332 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 424 ms 29320 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 359 ms 29348 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 340 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 1 ms 340 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 3 ms 1556 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1556 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 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 980 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 2 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 968 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 332 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 328 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 1024 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 968 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 964 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 2 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 980 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 960 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 1016 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 512 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 422 ms 29896 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 204 ms 4600 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 220 ms 4624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 180 ms 12660 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 418 ms 29344 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 324 ms 29268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 348 ms 29352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 431 ms 29332 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 424 ms 29320 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 359 ms 29348 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 42 ms 3924 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 1 ms 324 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 332 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 3 ms 1544 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 5 ms 1684 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 1684 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 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 2 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 2 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 2 ms 712 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 2 ms 980 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 976 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 968 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 980 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 464 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 475 ms 30036 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 194 ms 4596 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 188 ms 4564 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 192 ms 12640 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 425 ms 29344 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 344 ms 29296 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 316 ms 29352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 343 ms 29324 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 404 ms 29324 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 408 ms 29356 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2107 ms 659888 KB Time limit exceeded
97 Halted 0 ms 0 KB -