oj.uz

Submission #1104984

# Submission time Handle Problem Language Result Execution time Memory
1104984 2024-10-25T03:30:27 Z koukirocks Boarding Passes (BOI22_passes) C++17
25 / 100
 9 ms 58936 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

int pas[15][15][MAX],rpas[15][15][MAX];
vector<int> pos[20];
int g;

ldb calc(ldb x,int st,int can) {
    ldb ans=0;
    ll k=(x?pos[can][x-1]:0);
    // cout<<x<<" "<<k<<" xk\n";
    for (int i=0;i<g;i++) {
        if (st&(1<<i)) {
            ans+=pas[i][can][k]+rpas[i][can][k+1];
        }
    }
    ldb n = pos[can].size();
    return ans+x*(x-1)/4+(n-x)*(n-x-1)/4;
}

int main() {
    speed;
    string s;
    cin>>s;
    vector<int> d;
    for (char c:s) d.push_back(c);
    sort(all(d));
    d.resize(unique(all(d))-d.begin());
    int n=s.size();
    for (int i=0;i<n;i++) {
        pos[lower_bound(all(d),s[i])-d.begin()].push_back(i);
    }
    g=d.size();
    // for (int i=0;i<g;i++) {
    //     for (int j:pos[i]) cout<<j<<" ";
    //     cout<<" pos\n";
    // }
    // cout<<"g "<<g<<"\n";
    for (int i=0;i<g;i++) {
        for (int j=0;j<g;j++) {
            int iid=0,jid=0;
            pas[i][j][0]=0;
            ll cnt=0;
            for (int k=0;k<n;k++) {
                if (iid<pos[i].size() and pos[i][iid]==k) {
                    cnt++;
                    iid++;
                }
                if (jid<pos[j].size() and pos[j][jid]==k) {
                    if (k>0) pas[i][j][k]=pas[i][j][k-1]+cnt;
                    jid++;
                } else pas[i][j][k]=pas[i][j][k-1];
                // cout<<i<<" "<<j<<" "<<k<<" "<<iid<<" "<<jid<<" "<<cnt<<" "<<pas[i][j][k]<<" pas\n";
            }
        }
    }
    for (int i=0;i<g;i++) {
        for (int j=0;j<g;j++) {
            int iid=pos[i].size()-1,jid=pos[j].size()-1;
            rpas[i][j][n]=0;
            ll cnt=0;
            for (int k=n-1;k>=0;k--) {
                if (iid>=0 and pos[i][iid]==k) {
                    cnt++;
                    iid--;
                }
                if (jid>=0 and pos[j][jid]==k) {
                    rpas[i][j][k]=rpas[i][j][k+1]+cnt;
                    jid--;
                } else rpas[i][j][k]=rpas[i][j][k+1];
            }
        }
    }
    ldb dp[1<<16];
    for (int st=1;st<(1<<g);st++) dp[st]=oo;
    dp[0]=0;
    for (int st=0;st<(1<<g);st++) {
        for (int i=0;i<g;i++) {
            if (st&(1<<i)) continue;
            int l=0,r=pos[i].size();
            // cout<<l<<" "<<r<<" l r\n";
            while (l+2<r) {
                int mid1=(l+r)/2;
                int mid2=mid1+1;
                // cout<<st<<" "<<i<<" st can\n";
                // cout<<mid1<<" "<<calc(mid1,st,i)<<" mid1\n";
                // cout<<mid2<<" "<<calc(mid2,st,i)<<" mid2\n";
                if (calc(mid1,st,i)<calc(mid2,st,i)) r=mid2;
                else l=mid1;
            }
            for (int k=l;k<=r;k++) {
                // cout<<k<<" "<<calc(k,st,i)<<" k calc\n";
                dp[st|(1<<i)]=min(dp[st|(1<<i)],dp[st]+calc(k,st,i));
            }
        }
    }
    cout<<dp[(1<<g)-1]<<"\n";
    return 0;
}

// HEHEHEHIHILOL

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 if (iid<pos[i].size() and pos[i][iid]==k) {
      |                     ~~~^~~~~~~~~~~~~~
passes.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 if (jid<pos[j].size() and pos[j][jid]==k) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3408 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 2 ms 11600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 3328 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 7 ms 58704 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 6 ms 58704 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 6 ms 58704 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 7 ms 58928 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 6 ms 58704 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 48672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 58704 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 7 ms 58704 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 58704 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 6 ms 58704 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 58704 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 58704 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 58704 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 58912 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 6 ms 58872 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 3328 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 7 ms 58704 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 6 ms 58704 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 6 ms 58704 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 7 ms 58928 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 6 ms 58704 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 5 ms 48672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 58704 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 7 ms 58704 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 7 ms 58704 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 6 ms 58704 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 58704 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 7 ms 58704 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 6 ms 58704 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 58912 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 6 ms 58872 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 11600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 2 ms 3408 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 7 ms 58936 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 7 ms 58704 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 7 ms 58840 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 7 ms 58704 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 6 ms 58704 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 7 ms 48464 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 9 ms 58704 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 7 ms 58872 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 8 ms 58872 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 7 ms 58704 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 7 ms 58704 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 58704 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 58760 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 8 ms 58888 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 8 ms 58704 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 3 ms 3664 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 2 ms 3664 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 2 ms 3408 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -