oj.uz

Submission #835999

# Submission time Handle Problem Language Result Execution time Memory
835999 2023-08-24T04:35:44 Z Magikarp4000 Boarding Passes (BOI22_passes) C++17
100 / 100
 617 ms 28736 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+5, MAXG = 15;
int n,g;
string str;
vector<int> comp[MAXG];
double dp[1<<MAXG], pg[MAXG][MAXG][MAXN], sg[MAXG][MAXG][MAXN];
UM<char,int> mp;

void precalc() {
    FOR(i,0,g) {
        FOR(j,0,g) {
            vector<double> wp(n+2), ws(n+2);
            double val = j == i ? 0.5 : 1.0;
            FORX(u,comp[j]) wp[u+1] = ws[u+1] = val;
            FOR(k,1,n+1) wp[k] += wp[k-1];
            FORR(k,n,0) ws[k] += ws[k+1];
            int cn = comp[i].size();
            FOR(k,1,cn+1) pg[i][j][k] = pg[i][j][k-1]+wp[comp[i][k-1]+1];
            FORR(k,cn,0) sg[i][j][k] = sg[i][j][k+1]+ws[comp[i][k-1]+1];
        }
    }
}

double f(int x, int s, int i) {
    double cur = 0.0;
    FOR(j,0,g) {
        if (!(s&(1<<j))) continue;
        cur += pg[i][j][x]+sg[i][j][x+1];
        if (j == i) cur -= 0.5*double(comp[i].size());
    }
    return cur;
}

double tsearch(int s, int i) {
    int l = 0, r = comp[i].size();
    while (r-l >= 3) {
        int m1 = l+(r-l)/3, m2 = r-(r-l)/3;
        if (f(m1,s,i) > f(m2,s,i)) l = m1;
        else r = m2;
    }
    double ans = LLINF;
    FOR(x,l,r+1) ans = min(ans,f(x,s,i));
    return ans;
}

signed main() {
    OPTM;
    cin >> str;
    n = str.length();
    FOR(i,0,n) {
        if (!mp.count(str[i])) mp[str[i]] = g++;
        comp[mp[str[i]]].PB(i);
    }
    precalc();
    FOR(s,1,1<<g) dp[s] = LLINF;
    FOR(s,0,1<<g) {
        FOR(i,0,g) {
            if (!(s&(1<<i))) continue;
            dp[s] = min(dp[s], dp[s^(1<<i)]+tsearch(s,i));
        }
    }
    cout << fixed << setprecision(6) << dp[(1<<g)-1];
}

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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 336 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 4 ms 3472 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3984 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4240 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 4240 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 388 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 920 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 852 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 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 844 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 844 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 388 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 920 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 852 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 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 844 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 844 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 852 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 852 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 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 2 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 840 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 15 ms 3228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 14 ms 3200 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 12 ms 3328 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 15 ms 3200 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 14 ms 3236 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 14 ms 3212 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 15 ms 3236 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 15 ms 3228 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 15 ms 3228 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 15 ms 3228 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 336 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 4 ms 3472 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3984 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4240 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 4240 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 388 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 920 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 852 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 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 844 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 844 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 852 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 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 852 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 852 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 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 2 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 840 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 15 ms 3228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 14 ms 3200 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 12 ms 3328 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 15 ms 3200 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 14 ms 3236 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 14 ms 3212 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 15 ms 3236 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 15 ms 3228 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 15 ms 3228 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 15 ms 3228 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 720 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 42 ms 3028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 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 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 3472 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 3984 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 4240 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 4240 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 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 836 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 852 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 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 976 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 15 ms 3228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 15 ms 3236 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 11 ms 3292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 15 ms 3200 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 14 ms 3236 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 15 ms 3236 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 15 ms 3236 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 15 ms 3228 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 14 ms 3228 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 14 ms 3228 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 577 ms 28736 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 34 ms 2644 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 617 ms 28560 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 304 ms 28516 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 41 ms 3048 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 580 ms 28556 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 572 ms 28492 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 577 ms 28536 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 572 ms 28568 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 595 ms 28704 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 568 ms 28564 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 585 ms 28584 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 361 ms 26620 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 568 ms 28612 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'