oj.uz

Submission #823753

# Submission time Handle Problem Language Result Execution time Memory
823753 2023-08-13T04:48:23 Z Amylopectin Boarding Passes (BOI22_passes) C++14
30 / 100
 2000 ms 50060 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int mxn = 1e6 + 10;
vector<int> ar[mxn] = {},cli[mxn] = {};
double avinv[mxn] = {},fst[mxn] = {},ami = -1;
char s[mxn] = {},alp[mxn] = {};
int u[mxn] = {};
int re(int cn,int dep,int cru,double cva)
{
    int i,j,cm,fn,fm,fru,fva;
    double cmi = 0;
    if(dep == cru)
    {
        if(ami == -1)
        {
            ami = cva;
        }
        else 
        {
            ami = min(cva,ami);
        }
        return 0;
    }
    for(i=1; i<cru; i++)
    {
        if(u[i] == 1)
        {
            continue;
        }
        u[i] = 1;
        cli[dep].clear();
        fru = 0;
        fva = 0;
        for(j=0; j<ar[i].size(); j++)
        {
            fn = ar[i][j];
            while(fru < cli[dep-1].size() && cli[dep-1][fru] < fn)
            {
                cli[dep].push_back(cli[dep-1][fru]);
                fru ++;
            }
            cli[dep].push_back(fn);
            fva += fru;
            fst[j] = fva + avinv[j+1];
        }
        while(fru < cli[dep-1].size())
        {
            cli[dep].push_back(cli[dep-1][fru]);
            fru ++;
        }
        fru = cli[dep-1].size()-1;
        fva = 0;
        cmi = fst[ar[i].size()-1];
        for(j=ar[i].size()-1; j>=0; j--)
        {
            fn = ar[i][j];
            while(fru >= 0 && cli[dep-1][fru] > fn)
            {
                fru --;
            }
            fva += cli[dep-1].size() - fru - 1;
            if(j > 0)
            {
                cmi = min(cmi,fst[j-1] + fva + avinv[ar[i].size() - j]);
            }
            else 
            {
                cmi = min(cmi, fva + avinv[ar[i].size() - j]);
            }
        }
        re(i,dep+1,cru,cva + cmi);
        u[i] = 0;
    }
    return 0;
}
int main()
{
    int i,j,n,m,cn,cm,fn,fm,cru = 1;
    double p;
    scanf("%s",&s);
    n = strlen(s);
    for(i=2; i<=n; i++)
    {
        p = i;
        avinv[i] = p*(p-1) / 4;
    }
    for(i=0; i<n; i++)
    {
        cn = s[i] - 'A' + 1;
        if(alp[cn] == 0)
        {
            alp[cn] = cru;
            cru ++;
        }
        cm = alp[cn];
        ar[cm].push_back(i);
    }
    re(-1,1,cru,0);
    printf("%.3lf\n",ami);
}

Compilation message

passes.cpp: In function 'int re(int, int, int, double)':
passes.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(j=0; j<ar[i].size(); j++)
      |                  ~^~~~~~~~~~~~~
passes.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             while(fru < cli[dep-1].size() && cli[dep-1][fru] < fn)
      |                   ~~~~^~~~~~~~~~~~~~~~~~~
passes.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while(fru < cli[dep-1].size())
      |               ~~~~^~~~~~~~~~~~~~~~~~~
passes.cpp:14:13: warning: unused variable 'cm' [-Wunused-variable]
   14 |     int i,j,cm,fn,fm,fru,fva;
      |             ^~
passes.cpp:14:19: warning: unused variable 'fm' [-Wunused-variable]
   14 |     int i,j,cm,fn,fm,fru,fva;
      |                   ^~
passes.cpp: In function 'int main()':
passes.cpp:84:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000010]' [-Wformat=]
   84 |     scanf("%s",&s);
      |            ~^  ~~
      |             |  |
      |             |  char (*)[1000010]
      |             char*
passes.cpp:82:11: warning: unused variable 'j' [-Wunused-variable]
   82 |     int i,j,n,m,cn,cm,fn,fm,cru = 1;
      |           ^
passes.cpp:82:15: warning: unused variable 'm' [-Wunused-variable]
   82 |     int i,j,n,m,cn,cm,fn,fm,cru = 1;
      |               ^
passes.cpp:82:23: warning: unused variable 'fn' [-Wunused-variable]
   82 |     int i,j,n,m,cn,cm,fn,fm,cru = 1;
      |                       ^~
passes.cpp:82:26: warning: unused variable 'fm' [-Wunused-variable]
   82 |     int i,j,n,m,cn,cm,fn,fm,cru = 1;
      |                          ^~
passes.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%s",&s);
      |     ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47308 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 24 ms 47200 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 27 ms 47256 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 23 ms 47188 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 24 ms 47308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 26 ms 49612 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 27 ms 50060 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 25 ms 49936 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 31 ms 49904 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47280 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 24 ms 47388 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 27 ms 47288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 28 ms 47188 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 25 ms 47268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 23 ms 47276 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 25 ms 47276 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 23 ms 47260 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 24 ms 47280 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 28 ms 47196 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 23 ms 47224 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 47284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 47224 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 24 ms 47312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 23 ms 47268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 24 ms 47264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 27 ms 47400 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47280 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 24 ms 47388 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 27 ms 47288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 28 ms 47188 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 25 ms 47268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 23 ms 47276 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 25 ms 47276 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 23 ms 47260 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 24 ms 47280 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 28 ms 47196 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 23 ms 47224 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 47284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 47224 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 24 ms 47312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 23 ms 47268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 24 ms 47264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 27 ms 47400 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 22 ms 47188 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 22 ms 47296 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 26 ms 47260 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 26 ms 47304 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 26 ms 47188 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 22 ms 47284 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 25 ms 47300 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 24 ms 47192 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 24 ms 47188 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 25 ms 47288 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 23 ms 47192 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 25 ms 47244 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 28 ms 47188 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 23 ms 47304 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 24 ms 47308 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 24 ms 47284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 29 ms 47272 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 26 ms 47572 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 23 ms 47536 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2069 ms 47744 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47308 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 24 ms 47200 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 27 ms 47256 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 23 ms 47188 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 24 ms 47308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 26 ms 49612 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 27 ms 50060 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 25 ms 49936 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 31 ms 49904 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 27 ms 47280 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 24 ms 47388 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 27 ms 47288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 28 ms 47188 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 25 ms 47268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 23 ms 47276 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 25 ms 47276 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 23 ms 47260 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 24 ms 47280 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 28 ms 47196 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 23 ms 47224 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 24 ms 47284 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 23 ms 47224 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 24 ms 47312 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 23 ms 47268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 24 ms 47264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 27 ms 47400 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 22 ms 47188 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 22 ms 47296 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 26 ms 47260 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 26 ms 47304 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 26 ms 47188 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 22 ms 47284 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 25 ms 47300 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 24 ms 47192 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 24 ms 47188 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 25 ms 47288 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 23 ms 47192 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 25 ms 47244 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 28 ms 47188 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 23 ms 47304 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 24 ms 47308 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 24 ms 47284 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 29 ms 47272 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 26 ms 47572 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 23 ms 47536 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2069 ms 47744 KB Time limit exceeded
47 Halted 0 ms 0 KB -