oj.uz

Submission #1054189

# Submission time Handle Problem Language Result Execution time Memory
1054189 2024-08-12T07:27:10 Z sofijavelkovska Boarding Passes (BOI22_passes) C++17
100 / 100
 170 ms 141148 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5, MAXK=15;
const long long INF=1e18;

string s;
int n, k;
vector<vector<int> > groups;
double geninv[MAXN+1], inv[MAXK][MAXK][MAXN+1];
double memo[(1<<MAXK)];

double dp(int mask)
{
    if (memo[mask]!=-1)
        return memo[mask];
    if (mask==(1<<k)-1)
        return memo[mask]=0;
    double mintotal=INF;
    for (int i=0; i<k; i++)
    {
        if (mask&(1<<i))
            continue;
        int l=0;
        int r=groups[i].size();
        int g=groups[i].size();
        double minsum=INF;
        while ((r-l)/3>0)
        {
            int t1=l+(r-l)/3;
            int t2=r-(r-l)/3;
            double sum1=0;
            for (int j=0; j<k; j++)
                if (mask&(1<<j))
                    sum1=sum1+inv[i][j][t1];
            sum1=sum1+geninv[t1]+geninv[g-t1];
            double sum2=0;
            for (int j=0; j<k; j++)
                if (mask&(1<<j))
                    sum2=sum2+inv[i][j][t2];
            sum2=sum2+geninv[t2]+geninv[g-t2];
            if (sum1<sum2)
            {
                minsum=min(minsum, sum1);
                r=t2;
            }
            else
                l=t1;
        }
        for (int t=l; t<=r; t++)
        {
            double sum=0;
            for (int j=0; j<k; j++)
                if (mask&(1<<j))
                    sum=sum+inv[i][j][t];
            sum=sum+geninv[t]+geninv[g-t];
            minsum=min(minsum, sum);
        }
        mintotal=min(mintotal, minsum+dp(mask|(1<<i)));
    }

    return memo[mask]=mintotal;
}

void calcinv(int a, int b)
{
    int prefix[n]={0};
    for (auto x : groups[b])
        prefix[x]=1;
    for (int i=1; i<n; i++)
        prefix[i]=prefix[i-1]+prefix[i];
    int m=prefix[n-1];
    long long maininv=0;
    int g=groups[a].size();
    for (auto x : groups[a])
        if (x!=0)
            maininv=maininv+prefix[x-1];
    inv[a][b][g]=maininv;
    for (int j=g-1; j>=0; j--)
    {
        int x=groups[a][j];
        if (x!=0)
            maininv=maininv-prefix[x-1];
        maininv=maininv+(m-prefix[x]);
        inv[a][b][j]=maininv;
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    n=s.size();
    map<char, vector<int> > groupsbychar;
    for (int i=0; i<n; i++)
        groupsbychar[s[i]].push_back(i);
    for (auto t : groupsbychar)
        groups.push_back(t.second);
    k=groups.size();
    for (int i=0; i<=n; i++)
        geninv[i]=(double)i*(i-1)/4;
    for (int i=0; i<k; i++)
        for (int j=0; j<k; j++)
            if (i!=j)
                calcinv(i, j);
    for (int i=0; i<(1<<k); i++)
        memo[i]=-1;
    cout << fixed << setprecision(5) << dp(0);

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2392 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 0 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 4008 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 3984 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 3984 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 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 49496 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 49496 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 49500 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 4 ms 49500 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 49652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 4 ms 49620 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 4 ms 49496 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 49672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 49500 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 49500 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 49648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 ms 49500 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 4 ms 49500 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 49500 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 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 49496 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 49496 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 49500 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 4 ms 49500 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 49652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 4 ms 49620 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 4 ms 49496 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 49672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 49500 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 49500 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 49648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 ms 49500 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 4 ms 49500 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 49500 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 4 ms 49500 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 4 ms 49500 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 4 ms 49500 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 4 ms 49500 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 4 ms 49684 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 3 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 4 ms 49500 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 4 ms 49500 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 3 ms 49500 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 4 ms 49672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 4 ms 49500 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 4 ms 49500 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 4 ms 49500 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 4 ms 49500 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 49620 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 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 9 ms 92840 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 10 ms 92864 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 8 ms 92836 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 9 ms 92764 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 9 ms 92764 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 10 ms 92760 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 9 ms 92764 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 9 ms 92764 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 9 ms 92764 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 9 ms 92764 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 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2392 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 0 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 4008 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 3984 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 3984 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 4 ms 49496 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 3 ms 49496 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 4 ms 49500 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 4 ms 49500 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 4 ms 49652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 3 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 4 ms 49620 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 4 ms 49496 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 4 ms 49672 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 5 ms 49500 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 3 ms 49500 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 4 ms 49648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 4 ms 49500 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 4 ms 49500 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 4 ms 49500 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 4 ms 49500 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 4 ms 49500 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 4 ms 49500 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 4 ms 49500 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 4 ms 49684 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 3 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 4 ms 49500 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 4 ms 49500 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 3 ms 49500 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 4 ms 49672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 4 ms 49500 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 4 ms 49500 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 4 ms 49500 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 4 ms 49500 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 3 ms 49620 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 9 ms 92840 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 10 ms 92864 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 8 ms 92836 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 9 ms 92764 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 9 ms 92764 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 10 ms 92760 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 9 ms 92764 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 9 ms 92764 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 9 ms 92764 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 9 ms 92764 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 3 ms 29020 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 25 ms 136268 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 1 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 1 ms 4008 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 1 ms 3984 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 1 ms 3984 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 3 ms 49584 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 4 ms 49500 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 4 ms 49500 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 4 ms 49496 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 4 ms 49496 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 3 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 4 ms 49676 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 4 ms 49496 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 4 ms 49684 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 4 ms 49500 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 4 ms 49500 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 4 ms 49680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 3 ms 49500 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 3 ms 49500 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 4 ms 49500 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 0 ms 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 9 ms 92952 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 9 ms 92892 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 8 ms 92764 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 9 ms 93016 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 9 ms 92764 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 9 ms 92764 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 9 ms 92984 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 9 ms 92764 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 9 ms 92936 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 9 ms 92832 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 156 ms 140852 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 21 ms 133980 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 140 ms 138832 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 48 ms 138124 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 22 ms 136472 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 157 ms 140632 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 150 ms 139256 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 155 ms 141148 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 155 ms 140632 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 170 ms 141144 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 155 ms 140880 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 149 ms 140632 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 80 ms 140132 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 156 ms 139184 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'