oj.uz

Submission #1078906

# Submission time Handle Problem Language Result Execution time Memory
1078906 2024-08-28T07:57:22 Z LIF Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 604 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+=(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]);
        }
    }
    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: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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 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 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2099 ms 604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

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 87 ms 432 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 81 ms 436 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 77 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 444 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 7 ms 464 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 12 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 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 87 ms 432 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 81 ms 436 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 77 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 444 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 7 ms 464 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 7 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 12 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 7 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 87 ms 444 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 93 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 77 ms 444 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 62 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 7 ms 464 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 8 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 7 ms 464 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 9 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 456 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 7 ms 464 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 8 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 128 ms 492 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 116 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2058 ms 348 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 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 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2099 ms 604 KB Time limit exceeded
7 Halted 0 ms 0 KB -