oj.uz

Submission #767606

# Submission time Handle Problem Language Result Execution time Memory
767606 2023-06-26T22:36:26 Z raysh07 Boarding Passes (BOI22_passes) C++17
100 / 100
 355 ms 26624 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, k;
const int K = 16;
const int N = 1e5 + 69;
int dp[1 << K]; //store 2 * value 
int F[N][K]; //fenwick for all positions 
vector <int> pos[K];
int add[K][K][N]; //value to add if i was already there, j is newly added, and we add it by prefix of size k, and rest suffix 

void upd(int x, int j){
    for (int i = x; i <= n; i += i & (-i)) F[i][j]++;
}

int query(int x, int j){
    int res = 0;
    for (int i = x; i; i -= i & (-i)) res += F[i][j];
    return res;
}

void pre(){
    for (int i = 0; i < k; i++){
        for (int j = 0; j < k; j++){
            if (i == j) continue;
            
            int sz = pos[j].size();
            int curr = 0;
            for (int pref = 1; pref <= sz; pref++){
                curr += query(pos[j][pref - 1], i);
                add[i][j][pref] = curr;
            }
            curr = 0;
            for (int pref = sz - 1; pref >= 0; pref--){
                curr += query(n, i) - query(pos[j][pref], i);
                add[i][j][pref] += curr;
            }
        }
    }
}

int f(int pref, int mask, int i){
    int ans = 0;
    int tot = pos[i].size();
    
    ans += pref * (pref - 1) / 2;
    ans += (tot - pref) * (tot - pref - 1) / 2;
    
    // if (i == 0){
    //     cout << pref << " " << ans << "\n";
    // }
    
    for (int j = 0; j < k; j++){
        if (mask >> j & 1){
            ans += 2 * add[j][i][pref];
        }
    }
    
    return ans;
}

int transition(int mask, int i){
    int l = 0, r = pos[i].size();
    
    while (r - l > 2){
        int m1 = (2 * l + r) / 3;
        int m2 = (l + 2 * r) / 3;
        
        int x1 = f(m1, mask, i);
        int x2 = f(m2, mask, i);
        
        if (x1 > x2) l = m1;
        else r = m2;
    }
    
    int ans = INF;
    
    for (int j = l; j <= r; j++) ans = min(ans, f(j, mask, i));
    
    // cout << mask << " " << i << " " << ans << " " << dp[mask] << "\n";
    
    return dp[mask] + ans;
}

void Solve() 
{
    string s; cin >> s;
    n = s.length();
    k = 15;
    for (int i = 0; i < n; i++){
        pos[s[i] - 'A'].push_back(i + 1);
        upd(i + 1, s[i] - 'A');
    }
    
    pre();
    
    for (int i = 1; i < (1 << k); i++) dp[i] = INF;
    
    for (int i = 1; i < (1 << k); i++){
        for (int j = 0; j < k; j++){
            if (i >> j & 1){
                dp[i] = min(dp[i], transition(i ^ (1 << j), j));
            }
        }
    }
    
    int ans = dp[(1 << k) - 1];
    if (ans & 1) cout << (ans/2) << ".5\n";
    else cout << (ans/2) << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1180 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 980 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 18 ms 980 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 20 ms 984 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 32 ms 1260 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 85 ms 20480 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 100 ms 24192 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 96 ms 25636 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 97 ms 25700 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1060 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 28 ms 976 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 64 ms 1592 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 59 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 33 ms 1300 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 25 ms 1312 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 61 ms 1356 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 42 ms 1236 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 44 ms 1356 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 44 ms 1356 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 40 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 1236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 42 ms 1324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 40 ms 1284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 41 ms 1344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 45 ms 1360 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1060 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 28 ms 976 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 64 ms 1592 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 59 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 33 ms 1300 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 25 ms 1312 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 61 ms 1356 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 42 ms 1236 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 44 ms 1356 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 44 ms 1356 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 40 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 1236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 42 ms 1324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 40 ms 1284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 41 ms 1344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 45 ms 1360 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 22 ms 1076 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 28 ms 1016 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 64 ms 1336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 60 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 33 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 25 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 61 ms 1364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 42 ms 1236 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 46 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 47 ms 1340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 38 ms 1356 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 41 ms 1328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 41 ms 1324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 43 ms 1328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 40 ms 1236 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 41 ms 1340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 41 ms 1300 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 38 ms 3604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 41 ms 3596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 155 ms 4036 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 138 ms 3968 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 46 ms 4100 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 155 ms 3916 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 154 ms 3972 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 152 ms 3920 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 155 ms 3932 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 152 ms 3928 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 176 ms 3916 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 152 ms 3964 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1180 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 980 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 18 ms 980 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 20 ms 984 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 32 ms 1260 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 85 ms 20480 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 100 ms 24192 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 96 ms 25636 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 97 ms 25700 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 24 ms 1060 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 28 ms 976 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 64 ms 1592 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 59 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 33 ms 1300 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 25 ms 1312 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 61 ms 1356 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 42 ms 1236 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 44 ms 1356 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 44 ms 1356 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 40 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 41 ms 1236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 41 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 42 ms 1324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 40 ms 1284 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 41 ms 1344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 45 ms 1360 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 22 ms 1076 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 28 ms 1016 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 64 ms 1336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 60 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 33 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 25 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 61 ms 1364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 42 ms 1236 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 46 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 47 ms 1340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 38 ms 1356 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 41 ms 1328 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 41 ms 1324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 43 ms 1328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 40 ms 1236 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 41 ms 1340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 41 ms 1300 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 38 ms 3604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 41 ms 3596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 155 ms 4036 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 138 ms 3968 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 46 ms 4100 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 155 ms 3916 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 154 ms 3972 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 152 ms 3920 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 155 ms 3932 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 152 ms 3928 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 176 ms 3916 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 152 ms 3964 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 30 ms 1236 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 40 ms 1788 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 31 ms 1180 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 16 ms 980 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 17 ms 988 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 20 ms 952 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 33 ms 1276 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 78 ms 20448 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 131 ms 24104 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 99 ms 25664 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 94 ms 25612 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 22 ms 980 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 33 ms 1000 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 69 ms 1348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 59 ms 1328 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 34 ms 1456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 24 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 61 ms 1360 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 41 ms 1240 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 41 ms 1356 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 47 ms 1344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 38 ms 1336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 41 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 41 ms 1232 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 44 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 39 ms 1236 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 41 ms 1284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 40 ms 1332 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 38 ms 3592 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 38 ms 3552 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 163 ms 3948 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 137 ms 3976 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 46 ms 4116 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 154 ms 3924 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 154 ms 3964 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 157 ms 4028 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 153 ms 3920 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 154 ms 3892 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 153 ms 3904 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 153 ms 4180 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 355 ms 26504 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 61 ms 1748 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 329 ms 26400 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 117 ms 26340 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 39 ms 1748 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 319 ms 26504 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 347 ms 26480 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 333 ms 26380 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 346 ms 26516 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 338 ms 26476 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 336 ms 26572 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 338 ms 26488 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 349 ms 26424 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 339 ms 26624 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'