Submission #1078902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078902		LIF	Boarding Passes (BOI22_passes)	C++14	0 / 100	1 ms	348 KiB

passes

#include<bits/stdc++.h>
using namespace std;
string s;
vector<char> vv;
bool flag[500050];
bool vis[500005];
vector<char> temp;
int len = 0;
bool used[500005];
int siz[500005];
char ch[500005];
double minn = 1e9;
void check()
{
    for(int j=0;j<s.size();j++)used[j] = false;
    double ans = 0;
    for(auto it : temp)
    {
        int xx = it - 'A' + 1;
        double pp = 1e9;
        for(double i=0;i<=siz[xx];i++)
        {
            //設有i個在前面，剩下的在後面
            double now = siz[xx] - i;
            double tt = 0;
            tt += i*(i-1)/4 + (now) *(now-1)/4;
            int fir = 0;
            for(int j=0;j<s.length();j++)
            {
                if(fir >= i)break;
                if(ch[j] == it)fir++;
                if(used[j] == true)
                {
                    tt+=(i-fir);
                }
            }
            int sec = 0;
            for(int j=s.length()-1;j>=0;j--)
            {
                if(sec >= now)break;
                if(ch[j] == it)sec++;
                if(used[j] == true)
                {
                    tt += (now-sec);
                }
            }
            pp = min(pp,tt);
        }
        ans += pp;
        for(int i=0;i<s.size();i++)
        {
            if(s[i] == it)used[i] = true;
        }
        //cout<<it<<" "<<ans<<endl;
    }
    if(ans < minn)
    {
        // for(auto it : temp)cout<<it<<" ";
        // cout<<endl;
    }
    minn = min(minn,ans);
}
void dfs(int now)
{
    if(now == len)
    {
        check();
        return;
    }
    for(int i=0;i<vv.size();i++)
    {
        int xx = vv[i] - 'A' + 1;
        if(vis[xx] == false)
        {
            vis[xx] = true;
            temp.push_back(vv[i]);
            dfs(now+1);
            temp.pop_back();
            vis[xx] = false;
        }

    }
}
int main()
{
    cin>>s;
    for(int i=0;i<s.length();i++)ch[i] = s[i];
    for(int i=0;i<s.length();i++)
    {
        int xx = s[i] - 'A' + 1;
        siz[xx]++;
        if(flag[xx] == false)
        {
            len++;
            flag[xx] = true;
            vv.push_back(s[i]);
        }
    }
    if(vv.size() == 1)
    {
        if(len %2 == 1)
        {
            double fir = len/2;
            double sec = len/2+1;
            double ans = (0+fir-1)*fir/4 + (0+sec-1)*sec / 4;
            printf("%.4lf",ans);
            return 0;
        }
        else
        {
            double fir = len/2;
            double sec = len/2;
            double ans = (0+fir-1)*fir/4 + (0+sec-1)*sec / 4;
            printf("%.4lf",ans);
            return 0;
        }
    }
    dfs(0);
    printf("%.4lf",minn);








    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'void check()':
passes.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0;j<s.size();j++)used[j] = false;
      |                 ~^~~~~~~~~
passes.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             for(int j=0;j<s.length();j++)
      |                         ~^~~~~~~~~~~
passes.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i=0;i<s.size();i++)
      |                     ~^~~~~~~~~
passes.cpp: In function 'void dfs(int)':
passes.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<vv.size();i++)
      |                 ~^~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<s.length();i++)ch[i] = s[i];
      |                 ~^~~~~~~~~~~
passes.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<s.length();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40