oj.uz

답안 #723369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723369 2023-04-13T16:17:39 Z drdilyor Boarding Passes (BOI22_passes) C++17
5 / 100
 233 ms 376900 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define time(code) {auto _s = chrono::high_resolution_clock::now(); code;cerr << (chrono::high_resolution_clock::now() - _s).count() / 1e9 << '\n';}
 
inline ll exp_inv(ll x) {
    return x * (x-1);
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    char a = 'A';
    string s; cin >> s;
    const int G = 15, N = 1e5;
    int n = s.size();
    if (n == 1) {
        cout << "0\n";
        return 0;
    }

    ll suml[G][G][N];
    ll sumr[G][G][N];
    ll cr[G][N];
    ll cl[G][N];
    int cnt[G]{};
    vector ix(G, vector<int>());

    time(({
        for (int c1 = 0; c1 < G; c1++) {
            for (int c2 = 0; c2 < G; c2++) {
                ll res = 0, cur = 0;
                for (int i = 0; i < n; i++) {
                    if (s[i] == c1+a)
                        res += cur;
                    else if (s[i] == c2+a)
                        cur++;
                    suml[c1][c2][i] = res;
                }
            }
        }
        for (int c1 = 0; c1 < G; c1++) {
            for (int c2 = 0; c2 < G; c2++) {
                ll res = 0, cur = 0;
                for (int i = n-1; i >= 0; i --) {
                    if (s[i] == c1+a)
                        res += cur;
                    else if (s[i] == c2+a)
                        cur++;
                    sumr[c1][c2][i] = res;
                }
            }
        }
        for (int j = 0; j < G; j++) {
            int c = 0;
            for (int i = 0; i < n;i ++) {
                if (s[i] == j+a)
                    c++;
                cl[j][i] = c;
            }
        }
        for (int j = 0; j < G; j++) {
            int c = 0;
            for (int i = n-1; i >= 0; i--) {
                if (s[i] == j+a)
                    c++;
                cr[j][i] = c;
            }
        }
        for (int i = 0; i < n; i++)
            cnt[s[i] - a]++;
        for (int i = 0; i < G; i++)
            ix[i].reserve(cnt[i]);
        for (int i = 0; i < n ;i++) 
            ix[s[i] - a].push_back(i);
    }));

    vector memo(1<<G, (ll)1e18);
    memo[(1<<G)-1] = 0;
    for (int used = (1<<G)-1-1; used >= 0; used--) {
        ll& res = memo[used];
        for (int i = 0 ;i < G; i++) {
            if (used&1<<i) continue;

            auto f = [&](int j) {
                ll sum = 0;
                for (int k = used; k; k &= k-1) {
                    int c2 = __builtin_ctz(k)&1;
                    if (used>>c2&1) {
                        if (j) sum += suml[i][c2][j-1];
                        if (j <n)sum += sumr[i][c2][j];
                    }
                }
                return sum * 4 + (j < n ? exp_inv(cr[i][j]) : 0) + (j ? exp_inv(cl[i][j-1]) : 0);
            };

            int l = -1, r = (int)ix[i].size()-2;
            while (l < r-1) {
                int m = (l+r) / 2;
                ll a = f(ix[i][m]), b = f(ix[i][m+1]);
                if (a == b) break;
                else if (a < b) r = m;
                else l = m;
            }
 
            for (int j = max(l-1, 0); j < min((int)ix[i].size(), 2 + max(0, r)); j++) {
                res = min(res, f(ix[i][j]) + memo[used |1<<i]);
            }
            res = min(res, f(0) + memo[used | 1<<i]);
            res = min(res, f(n) + memo[used | 1<<i]);
        }
    };
    ll ans;
    ans = memo[0];
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
    cout << endl;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 376268 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 148 ms 375976 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 187 ms 376308 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 159 ms 376308 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 171 ms 376340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 220 ms 376872 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 226 ms 376892 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 233 ms 376832 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 231 ms 376900 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 376304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 174 ms 376196 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 188 ms 376236 KB 1st numbers differ - expected: '1023.0000000000', found: '207.5000000000', error = '0.7971652004'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 376304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 174 ms 376196 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 188 ms 376236 KB 1st numbers differ - expected: '1023.0000000000', found: '207.5000000000', error = '0.7971652004'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 376268 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 148 ms 375976 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 187 ms 376308 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 159 ms 376308 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 171 ms 376340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 220 ms 376872 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 226 ms 376892 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 233 ms 376832 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 231 ms 376900 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 168 ms 376304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 174 ms 376196 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Incorrect 188 ms 376236 KB 1st numbers differ - expected: '1023.0000000000', found: '207.5000000000', error = '0.7971652004'
13 Halted 0 ms 0 KB -