oj.uz

Submission #748664

# Submission time Handle Problem Language Result Execution time Memory
748664 2023-05-26T17:31:12 Z inventiontime Boarding Passes (BOI22_passes) C++17
5 / 100
 5 ms 1680 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    #define int ll
    #define endl '\n' //comment for interactive
    #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
     
    #define pb push_back
    #define re resize
    #define ff first
    #define ss second
     
    #define all(x) (x).begin(), (x).end()
    #define all1(x) (x).begin()+1, (x).end()
    #define loop(i, n) for(int i = 0; i < n; i++)
    #define loop1(i, n) for(int i = 1; i <= n; i++)
     
    #define print(x) cout << #x << ": " << x << endl << flush
     
    typedef long long ll;
    typedef vector<int> vi;
    typedef vector<double> vd;
    typedef array<int, 2> ii;
    typedef array<int, 3> ti;
    typedef vector<ii> vii;
    typedef vector<ti> vti;
    typedef vector<vi> vvi;
    typedef priority_queue<int> pq;
     
    template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
    template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }
     
    const int inf = 1e17;
     
    double cst(int x) {
        return (double) x * (x-1) / 4;
    }
     
    void solve() {
     
     
        string s;
        cin >> s;
        int n = s.size();
        vvi pos(26);
        loop(i, n) 
            pos[s[i]-'A'].pb(i);
        vi ch;
        loop(i, 26) if(!pos[i].empty())
            ch.pb(i);
        int g = ch.size();
        vi id(26);
        loop(i, g) id[ch[i]] = i;
     
        if(g == 1) {
            cout << setprecision(16) << cst(n/2) + cst((n+1)/2) << endl;
            return;
        }
     
     
        vd dp(1 << g, inf);
        dp[0] = 0;

        auto cost = [&] (int pre, int ch, int idx) -> double {
            bitset<15> prev(pre);
            double ans = 0;
            int cnt = 0, oth = 0;
            for(int i = 0; i <= idx; i++) {
                if(prev[id[s[i]-'A']]) oth++;
                else if(id[s[i]-'A'] == ch) {
                    cnt++;
                    ans += oth;
                }
            }
            ans += cst(cnt);

            cnt = 0, oth = 0;
            for(int i = n-1; i > idx; i--) {
                if(prev[id[s[i]-'A']]) oth++;
                else if(id[s[i]-'A'] == ch) {
                    cnt++;
                    ans += oth;
                }
            }
            ans += cst(cnt);
            return ans;
        };

        loop(pre, 1 << g) {
            bitset<15> prev(pre);
            loop(ch, g) if(!prev[ch]) {
                int nxt = pre + (1 << ch); 
                int l = 0;
                int r = n-1;
                while(r - l >= 3) {
                    int m1 = l + (r-l)/3;
                    int m2 = l + (r-l)/3 * 2;
                    double a = cost(pre, ch, m1);
                    double b = cost(pre, ch, m2);
                    if(a < b)
                        r = m2;
                    else
                        l = m1;
                }
                for(int idx = l; idx <= r; idx++)
                    ckmin(dp[nxt], dp[pre] + cost(pre, ch, idx));
            }
        }
     
     
        cout << setprecision(16) << dp[(1 << g) - 1] << endl;
     
    }
     
    signed main() {
     
        fast_io;
     
        int t = 1; //cin >> t;
        while(t--)
            solve();
     
        return 0;
     
    }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1680 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1680 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1680 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Incorrect 3 ms 212 KB 1st numbers differ - expected: '703.0000000000', found: '713.0000000000', error = '0.0142247511'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Incorrect 3 ms 212 KB 1st numbers differ - expected: '703.0000000000', found: '713.0000000000', error = '0.0142247511'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1680 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1680 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1680 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 5 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Incorrect 3 ms 212 KB 1st numbers differ - expected: '703.0000000000', found: '713.0000000000', error = '0.0142247511'
17 Halted 0 ms 0 KB -