Submission #824104

#	Time	Username	Problem	Language	Result	Execution time	Memory
824104		Amylopectin	Boarding Passes (BOI22_passes)	C++14	100 / 100	225 ms	66272 KiB

passes

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <utility>
using namespace std;
const int mxn = 1e6 + 10;
struct we
{
    int idx,fcou[17] = {},bcou[17] = {};
};
vector<struct we> ar[mxn] = {};
vector<int> cli[mxn] = {};
double avinv[mxn] = {},fst[mxn] = {},ami = -1,dp[mxn] = {};
char s[mxn] = {};
int n,u[mxn] = {},alp[mxn] = {},f[17] = {};
double getva(int cfr,int ci,int cpo,int cru)
{
    int i,j,cn,cm;
    double fva = 0,bva = 0;
    for(i=0; i<cru; i++)
    {
        if((1<<i) & cfr)
        {
            if(cpo >= 0)
                fva += ar[ci][cpo].fcou[i];
            if(cpo + 1 < ar[ci].size())
                bva += ar[ci][cpo+1].bcou[i];
        }
    }
    return fva+bva + avinv[cpo+1] + avinv[ar[ci].size() - cpo-1];
}
int re(int cn,int dep,int cru,double cva)
{
    int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
    dep = 1;
    double cmi = 0,cva1,cva2;
    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);
            cl = -1;
            cr = ar[i].size() - 1;
            while(cl < cr)
            {
                mid = (cl+cr + 2) / 2 - 1;
                cva1 = getva(cfr,i,mid,cru);
                cva2 = getva(cfr,i,mid+1,cru);
                if(cva1 == cva2)
                {
                    cl = mid;
                    cr = mid;
                }
                else if(cva1 > cva2)
                {
                    cl = mid+1;
                }
                else 
                {
                    cr = mid;
                }
            }
            cmi = getva(cfr,i,cl,cru);
            // 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,k,o,m,cn,cm,fn,fm,cru = 0,la,fru = 0;
    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=0; i<cru; i++)
    {
        for(j=0; j<cru; j++)
        {
            if(i == j)
            {
                continue;
            }
            fru = 0;
            for(k=0; k<ar[i].size(); k++)
            {
                cn = ar[i][k].idx;
                while(fru < ar[j].size() && ar[j][fru].idx < cn)
                {
                    fru ++;
                }
                if(k > 0)
                {
                    ar[i][k].fcou[j] = ar[i][k-1].fcou[j];
                }
                ar[i][k].fcou[j] += fru;
            }
            fru = ar[j].size()-1;
            for(k=ar[i].size() - 1; k>=0; k--)
            {
                cn = ar[i][k].idx;
                while(fru >= 0 && ar[j][fru].idx > cn)
                {
                    fru --;
                }
                if(k < ar[i].size() - 1)
                {
                    ar[i][k].bcou[j] = ar[i][k+1].bcou[j];
                }
                ar[i][k].bcou[j] += ar[j].size() - fru - 1;
            }
        }
    }
    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 'double getva(int, int, int, int)':
passes.cpp:28:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             if(cpo + 1 < ar[ci].size())
      |                ~~~~~~~~^~~~~~~~~~~~~~~
passes.cpp:20:11: warning: unused variable 'j' [-Wunused-variable]
   20 |     int i,j,cn,cm;
      |           ^
passes.cpp:20:13: warning: unused variable 'cn' [-Wunused-variable]
   20 |     int i,j,cn,cm;
      |             ^~
passes.cpp:20:16: warning: unused variable 'cm' [-Wunused-variable]
   20 |     int i,j,cn,cm;
      |                ^~
passes.cpp: In function 'int re(int, int, int, double)':
passes.cpp:36:11: warning: unused variable 'j' [-Wunused-variable]
   36 |     int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
      |           ^
passes.cpp:36:13: warning: unused variable 'cm' [-Wunused-variable]
   36 |     int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
      |             ^~
passes.cpp:36:16: warning: unused variable 'fn' [-Wunused-variable]
   36 |     int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
      |                ^~
passes.cpp:36:19: warning: unused variable 'fm' [-Wunused-variable]
   36 |     int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
      |                   ^~
passes.cpp:36:22: warning: unused variable 'fru' [-Wunused-variable]
   36 |     int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
      |                      ^~~
passes.cpp:36:26: warning: unused variable 'fva' [-Wunused-variable]
   36 |     int i,j,cm,fn,fm,fru,fva,cfr,cl,cr,mid;
      |                          ^~~
passes.cpp: In function 'int main()':
passes.cpp:155:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000010]' [-Wformat=]
  155 |     scanf("%s",&s);
      |            ~^  ~~
      |             |  |
      |             |  char (*)[1000010]
      |             char*
passes.cpp:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |             for(k=0; k<ar[i].size(); k++)
      |                      ~^~~~~~~~~~~~~
passes.cpp:189:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |                 while(fru < ar[j].size() && ar[j][fru].idx < cn)
      |                       ~~~~^~~~~~~~~~~~~~
passes.cpp:207:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |                 if(k < ar[i].size() - 1)
      |                    ~~^~~~~~~~~~~~~~~~~~
passes.cpp:153:15: warning: unused variable 'o' [-Wunused-variable]
  153 |     int i,j,k,o,m,cn,cm,fn,fm,cru = 0,la,fru = 0;
      |               ^
passes.cpp:153:17: warning: unused variable 'm' [-Wunused-variable]
  153 |     int i,j,k,o,m,cn,cm,fn,fm,cru = 0,la,fru = 0;
      |                 ^
passes.cpp:153:25: warning: unused variable 'fn' [-Wunused-variable]
  153 |     int i,j,k,o,m,cn,cm,fn,fm,cru = 0,la,fru = 0;
      |                         ^~
passes.cpp:153:28: warning: unused variable 'fm' [-Wunused-variable]
  153 |     int i,j,k,o,m,cn,cm,fn,fm,cru = 0,la,fru = 0;
      |                            ^~
passes.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |     scanf("%s",&s);
      |     ~~~~~^~~~~~~~~

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