oj.uz

Submission #1028253

# Submission time Handle Problem Language Result Execution time Memory
1028253 2024-07-19T15:36:42 Z anango Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 17672 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<62;

void solve() {

    string S; cin >> S;
    int n = S.size();
    vector<int> ar(n); for (int i=0; i<n; i++) ar[i] = (S[i]-'A');
    int G = *max_element(ar.begin(), ar.end()); G++;
    int pref[n+1][G]; //count of character c, before index i
    int suff[n+1][G]; //count of character c, after or equal to index i
    for (int i=0; i<=n; i++) {
        for (int j=0; j<G; j++) {
            pref[i][j] = suff[i][j] = 0;
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<=G; j++) {
            if (j==ar[i]) {
                pref[i+1][j] = pref[i][j]+1;
            }
            else {
                pref[i+1][j] = pref[i][j];
            }
        }
    }
    
    for (int i=n-1; i>=0; i--) {
        for (int j=0; j<G; j++) {
            if (j==ar[i]) {
                suff[i][j] = suff[i+1][j]+1;
            }
            else {
                suff[i][j] = suff[i+1][j];
            }
        }
    }
    //everyone before L boards from the front, everyone after or equal to it boards from the back. 
    vector<vector<int>> counts(G,vector<int>(G,0));     //counts[i][j] = sum of subsequences of (i,j) before l, and subsequences of (j,i) after L
    //counts[i][j] = sum of pref[k][j] for k<=L and ar[k]=i, and analogous expression for the suffix
    //first, get initial count values (for everyone boarding from the back)
    //and assuming that these are already boarded since the back breaker may not be the same for each group - that was false assumption
    //so precomp counts then ternary search on the breakpoint
    for (int j=0; j<G; j++) {
        for (int k=0; k<n; k++) {
            int i = ar[k];
            //cout << "adding " << i <<" " << j <<" " << k <<" " << j << " " << suff[k][j] << endl;
            counts[i][j] += suff[k+1][j];
        }
    }
    vector<vector<vector<int>>> acounts;
    acounts.push_back(counts);
    for (int L=0; L<n; L++) {

        //counts[i][j] = number of swaps required if i goes after j



        //transfer L to the right
        int cur = ar[L];
        for (int j=0; j<G; j++) {
            int delta = suff[L+1][j];
            int delta2 = pref[L][j];
            counts[cur][j] -= delta-delta2;
        }
        acounts.push_back(counts);
        
        /*cout << "TRANSFERRED TO " << L+1 << endl;
        for (int i=0; i<G; i++) {
            for (int j=0; j<G; j++) {
                cout << i <<" " << j <<" " << counts[i][j] << endl;
            }
        }
        cout << endl;*/
    }
    vector<int> dp;
    dp=vector<int>(1<<G,INF); //dp[mask] = min cost if this mask is at the beginning of the ordering
    dp[0] = 0;
    for (int mask=0; mask<1<<G; mask++) {
        for (int addon=0; addon<G; addon++) {
            if (mask&(1<<addon)) continue;
            int l = 0; int r = n;
            vector<pair<int,int>> costs;
            while (l<r) {
                int m1,m2;
                if (r-l>1000000) {
                    m1 = l+(r-l)/5;
                    m2 = r-(r-l)/5;
                }
                else {
                    m1 = l;
                    m2 = r;
                }
                int am1 = 0;
                for (int j=0; j<G; j++) {
                    if (mask&(1<<j)) {
                        am1+=2*acounts[m1][addon][j];
                    }
                    if (j==addon) {
                        am1+=acounts[m1][addon][j];
                    }
                }
                int am2 = 0;
                for (int j=0; j<G; j++) {
                    if (mask&(1<<j)) {
                        am2+=2*acounts[m2][addon][j];
                    }
                    if (j==addon) {
                        am2+=acounts[m2][addon][j];
                    }
                }
                costs.push_back({m1,am1});
                costs.push_back({m2,am2});
                //cout << "adding " << mask <<" " << addon <<" " << l <<" " << r <<" " << m1 <<" " << m2 <<" " << am1 <<" " << am2 << endl;
                if (am1>am2) {
                    l=m1+1; r=r;
                }
                else if (am1<am2) {
                    l=l; r=m2-1;
                }
                else {
                    l=m1+1; r=m2;
                }
                //cout << mask <<" " << addon <<" " << al <<endl;
            }
            sort(costs.begin(), costs.end());
            costs.erase(unique(costs.begin(), costs.end()),costs.end());
            /*for (auto i:costs) {
                cout << i.first <<" " << i.second << endl;
            }*/
            int dec=0;
            int minimum=INF;
            for (int i=0; i<((int)costs.size())-1; i++) {
                if (costs[i].second<costs[i+1].second) dec=1;
                if (costs[i].second>costs[i+1].second && dec) assert(0==1);
                minimum=min(minimum,costs[i].second);
            }
            int al = 0;
            for (int j=0; j<G; j++) {
                if (mask&(1<<j)) {
                    al+=2*acounts[l][addon][j];
                }
                if (j==addon) {
                    al+=acounts[l][addon][j];
                }
            }
            assert(al==minimum);
            dp[mask | (1<<addon)] = min(dp[mask | (1<<addon)],dp[mask]+al);
        }
    }
    int ans=dp[(1<<G)-1];

    int a2 = ans/2;
    cout << a2;
    if (ans%2==1) cout << ".50";
    cout << endl;
}

signed main() {
    int local=0;
    if (local) {
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    }
    /*#ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif*/ //fast IO
    solve();
    
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passes.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 21 ms 15116 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 25 ms 16908 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 26 ms 17672 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 27 ms 17672 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 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 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 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 3 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 516 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 452 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 963 ms 11156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 921 ms 11140 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2017 ms 15224 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 21 ms 15116 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 25 ms 16908 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 26 ms 17672 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 27 ms 17672 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 4 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 3 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 3 ms 516 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 2 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 452 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 963 ms 11156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 921 ms 11140 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2017 ms 15224 KB Time limit exceeded
47 Halted 0 ms 0 KB -