oj.uz

Submission #1078883

# Submission time Handle Problem Language Result Execution time Memory
1078883 2024-08-28T07:44:44 Z LIF Boarding Passes (BOI22_passes) C++14
0 / 100
 2000 ms 2900 KB 
#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+=1;
            }
            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+=1;
            }
            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;
    }
    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]);
        }
    }
    dfs(0);
    printf("%.4lf",minn);








    return 0;
}

Compilation message

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:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i=0;i<s.size();i++)
      |                     ~^~~~~~~~~
passes.cpp: In function 'void dfs(int)':
passes.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<vv.size();i++)
      |                 ~^~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<s.length();i++)ch[i] = s[i];
      |                 ~^~~~~~~~~~~
passes.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<s.length();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 2496 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2013 ms 2900 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 77 ms 2396 KB 1st numbers differ - expected: '1023.0000000000', found: '378.5000000000', error = '0.6300097752'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 77 ms 2396 KB 1st numbers differ - expected: '1023.0000000000', found: '378.5000000000', error = '0.6300097752'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 2496 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2013 ms 2900 KB Time limit exceeded
7 Halted 0 ms 0 KB -