Submission #823753

#	Time	Username	Problem	Language	Result	Execution time	Memory
823753		Amylopectin	Boarding Passes (BOI22_passes)	C++14	30 / 100	2069 ms	50060 KiB

passes

#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 (stderr)

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 / 5
• Subtask 2: 25 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40