oj.uz

Submission #668207

# Submission time Handle Problem Language Result Execution time Memory
668207 2022-12-03T09:53:23 Z fatemetmhr Boarding Passes (BOI22_passes) C++17
55 / 100
 78 ms 45584 KB 
// Willkommen! hier ist der Ort, an dem du sterben wirst :)

#include <bits/stdc++.h>

using namespace std;

typedef long long   ll;
typedef long double ld;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 1e5 + 10;
const ll  inf   = 1e18;
const int lg    = 30;
const int al    = 15; /// REMEMBER YOU'VE CHANGED THISSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

vector <int> av[al + 2];
ll lef[al + 1][maxn5], rig[al + 1][maxn5];
ll pslef[al + 1][maxn5], psrig[al + 1][maxn5];
ll dp[1 << al];

inline bool check(int id, int lim, int mask){
    ll val = 2 * lim - int(av[id].size()) + 1;
    for(int i = 0; i < al; i++) if((mask >> i)&1)
        val += 2 * (lef[i][av[id][lim]] - rig[i][av[id][lim]]);
    return val <= 0;
}

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

    string s; cin >> s;
    int n = s.size();

    for(int i = 0; i < n; i++)
        av[s[i] - 'A'].pb(i);

    lef[s[0] - 'A'][0] = 1;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < al; j++){
            lef[j][i] = lef[j][i - 1] + (s[i] - 'A' == j);
        }
    }

    rig[s[n - 1] - 'A'][n - 1] = 1;
    for(int i = n - 2; i >= 0; i--){
        for(int j = 0; j < al; j++){
            rig[j][i] = rig[j][i + 1] + (s[i] - 'A' == j);
        }
    }

    for(int i = 0; i < al; i++) if(av[i].size()){
        for(int j = 0; j < al; j++)
            pslef[j][av[i][0]] = lef[j][av[i][0]];
        for(int j = 1; j < av[i].size(); j++) for(int k = 0; k < al; k++)
            pslef[k][av[i][j]] = pslef[k][av[i][j - 1]] + lef[k][av[i][j]];
        reverse(all(av[i]));
        for(int j = 0; j < al; j++)
            psrig[j][av[i][0]] = rig[j][av[i][0]];
        for(int j = 1; j < av[i].size(); j++) for(int k = 0; k < al; k++)
            psrig[k][av[i][j]] = psrig[k][av[i][j - 1]] + rig[k][av[i][j]];
        reverse(all(av[i]));
    }

    for(int mask = 1; mask < (1 << al); mask++){
        dp[mask] = inf;
        for(int i = 0; i < al; i++) if((mask >> i)&1){
            if(av[i].empty()){
                dp[mask] = dp[mask ^ (1 << i)];
                break;
            }
            int lo = -1, hi = av[i].size();
            while(hi - lo > 1){
                int mid = (lo + hi) >> 1;
                if(check(i, mid, mask ^ (1 << i)))
                    lo = mid;
                else
                    hi = mid;
            }
            ll len = av[i].size();
            ll val = hi * (hi - 1) + (len - hi) * (len - hi - 1);
            //cout << val << endl;
            if(lo > -1){
                for(int j = 0; j < al; j++) if(j != i && ((mask >> j)&1))
                    val += 4 * pslef[j][av[i][lo]];
            }
            //cout << val << endl;
            if(hi < av[i].size()){
                for(int j = 0; j < al; j++) if(j != i && ((mask >> j)&1))
                    val += 4 * psrig[j][av[i][hi]];
            }
            dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + val);
            //cout << "ok " << mask << ' ' << i << ' ' << lo << ' ' << val << ' ' << dp[mask] << endl;
        }
    }

    ll ans = dp[(1 << al) - 1];
    if(ans % 4 == 0)
        cout << ans / 4 << endl;
    else if(ans % 2 == 0)
        cout << ans / 4 << ".5" << endl;
    else
        cout << ans / 4 << ".25" << endl;
}

/*
HEHEHEHIHILOL
ABABABACACDED
*/

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j = 1; j < av[i].size(); j++) for(int k = 0; k < al; k++)
      |                        ~~^~~~~~~~~~~~~~
passes.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 1; j < av[i].size(); j++) for(int k = 0; k < al; k++)
      |                        ~~^~~~~~~~~~~~~~
passes.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             if(hi < av[i].size()){
      |                ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1364 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 3 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 4 ms 824 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 4 ms 852 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 7 ms 1344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 30 ms 38328 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 35 ms 45584 KB 1st numbers differ - expected: '1100977812.5000000000', found: '27235988.5000000000', error = '0.9752620006'
8 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 30 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 26 ms 932 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 18 ms 884 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 15 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 29 ms 932 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 12 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 25 ms 924 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 26 ms 920 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 23 ms 900 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 848 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 24 ms 912 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 25 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 25 ms 912 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 23 ms 840 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 27 ms 912 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 30 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 26 ms 932 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 18 ms 884 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 15 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 29 ms 932 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 12 ms 980 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 25 ms 924 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 26 ms 920 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 23 ms 900 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 848 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 24 ms 912 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 25 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 25 ms 912 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 23 ms 840 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 27 ms 912 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 6 ms 852 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 3 ms 852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 32 ms 880 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 25 ms 940 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 18 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 15 ms 864 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 28 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 12 ms 940 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 24 ms 940 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 27 ms 980 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 23 ms 904 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 26 ms 936 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 25 ms 880 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 25 ms 856 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 22 ms 936 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 23 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 25 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 3 ms 5716 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 3 ms 5716 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 78 ms 5620 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 64 ms 5628 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 27 ms 5716 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 65 ms 5540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 66 ms 5520 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 68 ms 5504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 68 ms 5556 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 68 ms 5580 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 74 ms 5840 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 73 ms 5584 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1364 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 3 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 4 ms 824 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 4 ms 852 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 7 ms 1344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 30 ms 38328 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 35 ms 45584 KB 1st numbers differ - expected: '1100977812.5000000000', found: '27235988.5000000000', error = '0.9752620006'
8 Halted 0 ms 0 KB -