oj.uz

Submission #1067151

# Submission time Handle Problem Language Result Execution time Memory
1067151 2024-08-20T12:06:05 Z mispertion Boarding Passes (BOI22_passes) C++17
25 / 100
 1 ms 920 KB 
#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize("Ofast")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = 1e16;
const int P = 2;

int mult(int a, int b){
    return a * 1LL * b % mod;
}

int sum(int a, int b){
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

int binpow(int a, int n){
    if (n == 0)
        return 1;
    if (n % 2 == 1){
        return mult(binpow(a, n - 1), a);
    }
    else{
        auto b = binpow(a, n / 2);
        return mult(b, b);
    }
}

const int K = 15;

int n, k, a[N], pr[K][N], sf[K][N], prr[K][K][N], sff[K][K][N];
ld dp[N];
vector<int> pos[K];



void solve(){
    string s;
    cin >> s;
    n = sz(s);
    vector<int> al = {};
    for(auto e : s){
        al.pb(e - 'A');
    }
    sort(all(al));
    al.resize(unique(all(al)) - al.begin());
    k = sz(al);
    for(int i = 0; i < k; i++)
        pos[i] = {0};
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(all(al), s[i - 1] - 'A') - al.begin();
        pos[a[i]].pb(i);
        pr[a[i]][i] = 1;
        sf[a[i]][i] = 1;
    }
    for(int i = 1; i <= n; i++)
        for(int x = 0; x < k; x++)
            pr[x][i] += pr[x][i - 1];
    for(int i = n; i >= 1; i--)
        for(int x = 0; x < k; x++)
            sf[x][i] += sf[x][i + 1];
    for(int y = 0; y < k; y++){
        for(int x = 0; x < k; x++){
            if(x == y) continue;
            for(int m = 1; m < sz(pos[x]); m++)
                prr[y][x][m] = prr[y][x][m - 1] + pr[y][pos[x][m]];
            for(int m = sz(pos[x]) - 1; m >= 1; m--)
                sff[y][x][m] = sff[y][x][m + 1] + sf[y][pos[x][m]];
        }
    }
    for(int mask = 1; mask < (1 << k); mask++){
        dp[mask] = infi;
        for(int x = 0; x < k; x++){
            if(!((mask >> x) & 1)) continue;
            int lo = 0, hi = sz(pos[x]) - 1;
            while(lo + 2 < hi){
                ld m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
                ld s1 = (m1 * (m1 - 1)) / 4.0 + (((ld)sz(pos[x]) - m1 - 1) * (((ld)sz(pos[x]) - m1 - 2))) / 4.0;
                for(int y = 0; y < k; y++){
                    if(y == x || !((mask >> y) & 1)) continue;
                    s1 += prr[y][x][(int)m1];
                    s1 += sff[y][x][(int)m1 + 1];
                }
                ld s2 = (m2 * (m2 - 1)) / 4 + ((sz(pos[x]) - m2 - 1) * ((sz(pos[x]) - m2 - 2))) / 4;
                for(int y = 0; y < k; y++){
                    if(y == x || !((mask >> y) & 1)) continue;
                    s2 += prr[y][x][(int)m2];
                    s2 += sff[y][x][(int)m2 + 1];
                }
                if(s1 > s2){
                    lo = m1;
                }else{
                    hi = m2;
                }
            }
            for(ld m1 = lo; m1 <= hi; m1++){
                ld s1 = (m1 * (m1 - 1)) / 4.0 + (((ld)sz(pos[x]) - m1 - 1) * (((ld)sz(pos[x]) - m1 - 2))) / 4.0;
                for(int y = 0; y < k; y++){
                    if(y == x || !((mask >> y) & 1)) continue;
                    s1 += prr[y][x][(int)m1];
                    s1 += sff[y][x][(int)m1 + 1];
                }
                dp[mask] = min(dp[mask], s1 + dp[mask ^ (1 << x)]);
            }
        }
    }
    cout << dp[(1 << k) - 1] << '\n';
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 920 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 896 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 872 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 860 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 1 ms 860 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -