Submission #824067

#	Time	Username	Problem	Language	Result	Execution time	Memory
824067		Amylopectin	Boarding Passes (BOI22_passes)	C++14	60 / 100	2087 ms	50128 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,dp[mxn] = {};
char s[mxn] = {};
int n,u[mxn] = {},alp[mxn] = {};
int re(int cn,int dep,int cru,double cva)
{
    int i,j,cm,fn,fm,fru,fva,cfr;
    dep = 1;
    double cmi = 0;
    if(dp[cn] != -1)
    {
        return dp[cn];
    }
    // if(dep == cru)
    // {
    //     if(ami == -1)
    //     {
    //         ami = cva;
    //     }
    //     else 
    //     {
    //         ami = min(cva,ami);
    //     }
    //     return 0;
    // }
    for(i=0; i<cru; i++)
    {
        if((1<<i) & cn)
        {
            cfr = cn - (1<<i);
            re(cfr,1,cru,0);
            cli[dep-1].clear();
            
            for(j=0; j<n; j++)
            {
                if((1<<(alp[s[j] - 'A' + 1])) & cfr)
                {
                    cli[dep-1].push_back(j);
                }
            }
            // 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]);
                }
            }
            if(dp[cn] == -1)
            {
                dp[cn] = cmi + dp[cfr];
            }
            else 
            {
                dp[cn] = min(dp[cn],cmi+dp[cfr]);
            }
            // re(i,dep+1,cru,cva + cmi);
            // u[i] = 0;
        }
    }
    return 0;
}
int main()
{
    int i,j,m,cn,cm,fn,fm,cru = 0,la;
    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<30; i++)
    {
        alp[i] = -1;
    }
    for(i=0; i<n; i++)
    {
        cn = s[i] - 'A' + 1;
        if(alp[cn] == -1)
        {
            alp[cn] = cru;
            cru ++;
        }
        cm = alp[cn];
        ar[cm].push_back(i);
    }
    for(i=1; i<min(33000,mxn); i++)
    {
        dp[i] = -1;
    }
    dp[0] = 0;
    la = (1<<cru) - 1;
    re(la,1,cru,0);
    printf("%.3lf\n",dp[la]);
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40