oj.uz

Submission #949904

# Submission time Handle Problem Language Result Execution time Memory
949904 2024-03-19T21:43:39 Z Dec0Dedd Boarding Passes (BOI22_passes) C++14
100 / 100
 232 ms 96952 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, int> pii;

const int N = 1e5+100;
const ll INF = 1e18;
const int G = 15;

vector<int> idx[N];

ll n, cross[G][G][N];
string s;

ll dist[1<<G];

ll nc2(ll x) {
    if (x < 2) return 0;
    return x*(x-1)/2;
}

ll calc(int msk, int u, int k) {
    ll res=0;
    for (int i=0; i<G; ++i) {
        if (!(msk&(1<<i))) continue;
        res+=2*cross[u][i][k];
    } int sz=idx[u].size();
    res+=nc2(k)+nc2(sz-k);
    return res;
}

// cost to go MSK -> MSK^u
ll cost(int msk, int u) {
    ll sz=idx[u].size();

    int l=0, r=sz-1, res=0;
    while (l <= r) {
        int m=(l+r)/2;
        if (calc(msk, u, m) > calc(msk, u, m+1)) res=m+1, l=m+1;
        else r=m-1;
    } return min(calc(msk, u, 0), calc(msk, u, res));
}

void solve() {
    cin>>s;
    n=s.size();

    for (int i=0; i<n; ++i) idx[s[i]-'A'].push_back(i+1);

    for (int a=0; a<G; ++a) {
        for (int b=0; b<G; ++b) {
            if (a == b) continue;
            ll ps[n+1]={};

            for (auto u : idx[b]) ++ps[u];
            for (int i=1; i<=n; ++i) ps[i]+=ps[i-1];
            int sz=idx[a].size();

            ll psum=0, ssum=0;
            for (auto x : idx[a]) ssum+=(ps[n]-ps[x-1]);
            cross[a][b][0]=ssum;

            for (int i=1; i<=sz; ++i) {
                int x=idx[a][i-1];
                psum+=ps[x], ssum-=(ps[n]-ps[x-1]);
                cross[a][b][i]=psum+ssum;
            }
        }
    }

    for (int i=0; i<(1<<G); ++i) dist[i]=INF;
    dist[0]=0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        pii x=pq.top(); pq.pop();
        ll d=x.first;
        int msk=x.second;

        if (dist[msk] < d) continue;
        for (int i=0; i<G; ++i) {
            if (msk&(1<<i)) continue;

            if (dist[msk^(1<<i)] > dist[msk]+cost(msk, i)) {
                dist[msk^(1<<i)]=dist[msk]+cost(msk, i);
                pq.push({dist[msk^(1<<i)], msk^(1<<i)});
            }
        }
    } assert(dist[(1<<G)-1] < INF);

    cout<<dist[(1<<G)-1]/2;
    if (dist[(1<<G)-1]%2) cout<<".5\n";
    else cout<<"\n";
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 79824 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 36 ms 83924 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 37 ms 83920 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 36 ms 85972 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 42 ms 85976 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 87 ms 84940 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 97 ms 87500 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 106 ms 85680 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 98 ms 85452 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 83928 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 42 ms 85932 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 58 ms 86228 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 57 ms 83968 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 50 ms 84180 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 44 ms 84184 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 52 ms 86228 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 52 ms 84184 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 56 ms 84184 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 58 ms 84688 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 53 ms 85968 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 53 ms 86220 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 52 ms 86228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 55 ms 84180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 53 ms 86232 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 52 ms 84184 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 56 ms 84180 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 83928 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 42 ms 85932 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 58 ms 86228 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 57 ms 83968 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 50 ms 84180 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 44 ms 84184 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 52 ms 86228 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 52 ms 84184 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 56 ms 84184 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 58 ms 84688 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 53 ms 85968 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 53 ms 86220 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 52 ms 86228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 55 ms 84180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 53 ms 86232 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 52 ms 84184 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 56 ms 84180 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 39 ms 83896 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 40 ms 85964 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 59 ms 86232 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 57 ms 84176 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 49 ms 84184 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 45 ms 86220 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 52 ms 83992 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 53 ms 86232 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 60 ms 84168 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 57 ms 84680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 55 ms 84180 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 59 ms 84172 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 50 ms 84124 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 55 ms 84180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 53 ms 84172 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 53 ms 86232 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 53 ms 84184 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 50 ms 85104 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 50 ms 85084 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 104 ms 84700 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 116 ms 86352 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 64 ms 84844 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 100 ms 84660 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 101 ms 84708 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 104 ms 86556 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 105 ms 86492 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 110 ms 84592 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 101 ms 84708 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 107 ms 84728 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 79824 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 36 ms 83924 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 37 ms 83920 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 36 ms 85972 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 42 ms 85976 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 87 ms 84940 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 97 ms 87500 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 106 ms 85680 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 98 ms 85452 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 40 ms 83928 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 42 ms 85932 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 58 ms 86228 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 57 ms 83968 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 50 ms 84180 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 44 ms 84184 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 52 ms 86228 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 52 ms 84184 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 56 ms 84184 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 58 ms 84688 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 53 ms 85968 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 53 ms 86220 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 52 ms 86228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 55 ms 84180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 53 ms 86232 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 52 ms 84184 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 56 ms 84180 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 39 ms 83896 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 40 ms 85964 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 59 ms 86232 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 57 ms 84176 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 49 ms 84184 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 45 ms 86220 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 52 ms 83992 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 53 ms 86232 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 60 ms 84168 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 57 ms 84680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 55 ms 84180 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 59 ms 84172 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 50 ms 84124 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 55 ms 84180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 53 ms 84172 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 53 ms 86232 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 53 ms 84184 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 50 ms 85104 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 50 ms 85084 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 104 ms 84700 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 116 ms 86352 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 64 ms 84844 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 100 ms 84660 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 101 ms 84708 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 104 ms 86556 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 105 ms 86492 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 110 ms 84592 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 101 ms 84708 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 107 ms 84728 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 49 ms 84176 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 54 ms 83896 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 42 ms 83924 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 33 ms 83920 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 35 ms 83928 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 39 ms 83900 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 43 ms 85976 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 89 ms 84936 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 97 ms 85392 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 100 ms 87496 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 99 ms 85460 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 39 ms 83860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 40 ms 85976 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 66 ms 84680 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 58 ms 84184 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 50 ms 88228 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 44 ms 84184 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 52 ms 84184 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 53 ms 86232 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 56 ms 84436 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 60 ms 84628 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 53 ms 84184 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 53 ms 88016 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 50 ms 86220 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 55 ms 84184 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 54 ms 84172 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 54 ms 86084 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 54 ms 84180 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 50 ms 85084 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 51 ms 85152 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 104 ms 84736 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 100 ms 84304 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 64 ms 84684 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 96 ms 84708 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 112 ms 86552 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 107 ms 84712 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 106 ms 84444 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 105 ms 86492 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 103 ms 84620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 105 ms 84700 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 220 ms 93692 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 78 ms 84184 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 228 ms 91688 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 129 ms 96952 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 56 ms 84176 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 199 ms 93488 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 213 ms 93928 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 216 ms 91836 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 232 ms 91688 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 209 ms 91472 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 211 ms 93192 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 211 ms 91688 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 204 ms 91088 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 215 ms 92752 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'