oj.uz

Submission #954663

# Submission time Handle Problem Language Result Execution time Memory
954663 2024-03-28T09:51:22 Z ifateen Boarding Passes (BOI22_passes) C++17
55 / 100
 26 ms 113244 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5, MAXG = 15;
map<char, int> m;
vector<int> pos[MAXG];
int n, cnt = 0, G, v[MAXN], PREF[MAXG][MAXG][MAXN], SUF[MAXG][MAXG][MAXN], pref[MAXN][MAXG];
double dp[1 << MAXG];
double compute(int i, int count, int mask) {
    double ret = 0;
    int rcnt = pos[i].size() - count;
    ret += count * (count - 1) * 0.25 + rcnt * (rcnt - 1) * 0.25;
    for (int j = 0; j < G; ++j)
        if (mask & (1 << j)) ret += (count ? PREF[i][j][count - 1] : 0) + (rcnt ? SUF[i][j][rcnt - 1] : 0);
    return ret;
}
signed main() {
    iostream::sync_with_stdio(false), cin.tie(nullptr);
    string s; cin >> s;
    n = s.length();
    for (int i = 0; i < n; ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
        G = max(G, v[i] + 1);
        pos[v[i]].push_back(i);
        pref[i][v[i]] = 1;
    }
    dp[0] = 0;
    for (int i = 1; i < n; ++i) for (int j = 0; j < G; ++j) pref[i][j] += pref[i - 1][j];
    for (int i = 0; i < G; ++i)
        for (int j = 0; j < G; ++j) {
            if (i == j) continue;
            for (int k = 0; k < pos[i].size(); ++k) {
                PREF[i][j][k] = pref[pos[i][k]][j] + (k ? PREF[i][j][k - 1] : 0);
            }
            for (int k = 0; k < pos[i].size(); ++k) {
                int idx = pos[i].size() - k - 1;
                SUF[i][j][k] = pref[n - 1][j] - (pos[i][idx] ? pref[pos[i][idx] - 1][j] : 0) + (k ? SUF[i][j][k - 1] : 0);
            }
        }
    for (int mask = 1; mask < (1 << G); mask++) {
        dp[mask] = 1e18;
        for (int i = 0; i < G; i++) {
            if (!(mask & (1 << i))) continue;
            double EV = compute(i, pos[i].size(), mask), c;
            int l = 0, r = pos[i].size() - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if ((c = compute(i, mid, mask)) <= compute(i, mid + 1, mask)) EV = min(EV, c), r = mid - 1;
                else l = mid + 1;
            }
            dp[mask] = min(dp[mask], EV + dp[mask ^ (1 << i)]);
        }
    }
    cout << fixed << setprecision(1) << dp[(1 << G) - 1];
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:32:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int k = 0; k < pos[i].size(); ++k) {
      |                             ~~^~~~~~~~~~~~~~~
passes.cpp:35:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for (int k = 0; k < pos[i].size(); ++k) {
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 7416 KB 1st numbers differ - expected: '772893586.0000000000', found: '-252553446.0000000000', error = '1.3267635423'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10856 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2516 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 7 ms 57944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 7 ms 57692 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 7 ms 57692 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 7 ms 57692 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 7 ms 57948 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 43356 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 57688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 6 ms 57808 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 57688 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 7 ms 57692 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 57692 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 57688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 57692 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 57692 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 57692 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10856 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2516 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 7 ms 57944 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 7 ms 57692 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 7 ms 57692 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 7 ms 57692 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 7 ms 57948 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 43356 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 57688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 6 ms 57808 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 57688 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 7 ms 57692 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 57692 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 57688 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 57692 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 57692 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 ms 57692 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 10588 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 7 ms 57688 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 6 ms 57892 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 7 ms 57692 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 7 ms 57944 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 6 ms 57692 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 5 ms 43472 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 6 ms 57692 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 6 ms 57688 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 7 ms 57692 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 6 ms 57916 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 6 ms 57692 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 7 ms 57692 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 57816 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 6 ms 57692 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 6 ms 57692 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2648 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 26 ms 109356 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 15 ms 109144 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 13 ms 109404 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 15 ms 109148 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 15 ms 109404 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 15 ms 111452 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 15 ms 113244 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 16 ms 113244 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 15 ms 113244 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 15 ms 113244 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 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 7416 KB 1st numbers differ - expected: '772893586.0000000000', found: '-252553446.0000000000', error = '1.3267635423'
7 Halted 0 ms 0 KB -