oj.uz

답안 #1078900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078900 2024-08-28T07:54:25 Z LIF Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 836 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 344 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 2098 ms 836 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 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 84 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 81 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 79 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 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 7 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 8 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 464 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 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 84 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 81 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 79 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 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 7 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 8 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 464 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 85 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 83 ms 440 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 77 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 62 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 8 ms 348 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 8 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 472 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 348 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 9 ms 344 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 115 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 128 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2009 ms 344 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 344 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 2098 ms 836 KB Time limit exceeded
7 Halted 0 ms 0 KB -