Submission #807516

#	Time	Username	Problem	Language	Result	Execution time	Memory
807516		Augustyn	Set (COCI21_set)	C++17	40 / 110	1086 ms	13452 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n,k,akt;
long long odp;
int istnieje[531441];
int trzecia(vector<int>p,vector<int>d)
{
    int ret=0;
    for(int i=0;i<p.size();++i)
    {
        if(p[i]==d[i])
            ret=ret*3+p[i]-1;
        else
            ret=ret*3+(p[i]^d[i])-1;
    }
    return ret;
}
int gle;
bool comp(vector<int>&a,vector<int>&b)
{
    for(int i=gle;i<k;++i)
        if(a[i]<b[i])
            return 1;
        else if(a[i]>b[i])
            return 0;
    return 0;
}
int trojdoint(vector<int>&a)
{
    int ret=0;
    for(int i=0;i<a.size();++i)
        ret=ret*3+a[i]-1;
    return ret;
}
vector<int>intdotroj(int a,int jdl)
{
    vector<int>ret;
    while(jdl)
    {
        ret.push_back((a%3)+1);
        a/=3;
        --jdl;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}
long long pot3[20];
void wejdz(int pocz,int kon,vector<int>&wek)
{
    if(kon-pocz+1<3)
        return;
    int najlep=gle;
    long long op_naj=__LONG_LONG_MAX__;
    long long ile[3];
    for(int i=gle;i<k;++i)
    {
        ile[0]=ile[1]=ile[2]=0;
        for(int j=pocz;j<=kon;++j)
        {
            ++ile[(wek[j]/pot3[k-i-1])%3];
        }
        sort(ile,ile+3);
        long long op=min(ile[0]*ile[1],(pot3[k-gle-1]-ile[2])*ile[0]);
        op=min(op,(pot3[k-gle-1]-ile[2])*(pot3[k-gle-1]-ile[1]));
       // cout<<ile[0]<<" "<<ile[1]<<" "<<ile[2]<<" "<<op<<endl;
        if(op<op_naj)
        {
            op_naj=op;
            najlep=i;
        }
    }
    ile[0]=ile[1]=ile[2]=0;
    vector<int>dol[3];
    int napozgle,napoznajlep;
    for(int i=pocz;i<=kon;++i)
    {
        napozgle=(wek[i]/pot3[k-gle-1])%3;
        napoznajlep=(wek[i]/pot3[k-najlep-1])%3;
        wek[i]=wek[i]+(napozgle-napoznajlep)*(pot3[k-najlep-1]-pot3[k-gle-1]);
        ++ile[napoznajlep];
    }
    sort(wek.begin()+pocz,wek.begin()+kon+1);
    for(int i=pocz;i<=kon;++i)
    {
        dol[(wek[i]/pot3[k-gle-1])%3].push_back(wek[i]%pot3[k-gle]);
    }
    //tutaj licze odp dla tego gowna
    int org_ile[3];
    for(int i=0;i<3;++i)
        org_ile[i]=ile[i];
    int zjd[3];
    for(int i=0;i<3;++i)
    zjd[i]=i;
    if(ile[0]>ile[1])
        swap(zjd[0],zjd[1]);
    if(ile[1]>ile[2])
        swap(zjd[1],zjd[2]);
    if(ile[0]>ile[1])
        swap(zjd[0],zjd[1]);
    ++akt;
    //cout<<gle<<" "<<ile[zjd[0]]<<" "<<ile[zjd[1]]<<" "<<ile[zjd[2]]<<" "<<pot3[k-gle-1]-ile[zjd[2]]<<endl;
    long long ilop[3];
    ilop[0]=(pot3[k-gle-1]-ile[zjd[2]])*(pot3[k-gle-1]-ile[zjd[1]]);
    ilop[1]=(pot3[k-gle-1]-ile[zjd[2]])*ile[zjd[0]];
    ilop[2]=ile[zjd[0]]*ile[zjd[1]];
    if(ilop[0]<ilop[1]&&ilop[0]<ilop[2])
    {
        odp+=ile[0]*ile[1];
        odp-=ile[0]*(pot3[k-gle-1]-ile[2]);
        odp+=(pot3[k-gle-1]-ile[1])*(pot3[k-gle-1]-ile[2]);

        for(auto i:dol[zjd[0]])
            istnieje[i]=akt;

        int najm=zjd[2]*pot3[k-gle-1];
        int najw=zjd[2];
        for(int i=1;i<k-gle;++i)
            najw=najw*3+2;
        int it_dol=0;
        vector<vector<int>>te;
        for(int i=najm;i<=najw;++i)
        {
            if(it_dol<dol[zjd[2]].size())
                if(dol[zjd[2]][it_dol]==i)
                {
                    ++it_dol;
                    continue;
                }
            te.push_back(intdotroj(i,k-gle));
        }
        najm=zjd[1]*pot3[k-gle-1];
        najw=zjd[1];
        for(int i=1;i<k-gle;++i)
            najw=najw*3+2;
        it_dol=0;
        
        for(int i=najm;i<=najw;++i)
        {
            if(it_dol<dol[zjd[1]].size())
                if(dol[zjd[1]][it_dol]==i)
                {
                    ++it_dol;
                    continue;
                }
            vector<int>wtf=intdotroj(i,k-gle);
            for(auto j:te)
                if(istnieje[trzecia(j,wtf)]!=akt)
                    --odp;
        }
    }
    else if(ilop[2]<ilop[1])
    {
        for(auto i:dol[zjd[2]])
            istnieje[i]=akt;
        for(auto i:dol[zjd[0]])
            for(auto j:dol[zjd[1]])
                if(istnieje[trzecia(intdotroj(i,k),intdotroj(j,k))]==akt)
                    ++odp;
    }
    else
    {
        //wszystkie z ile[0]xbrakujace z ile[2]
        for(auto i:dol[zjd[1]])
        {
            istnieje[i]=akt;
        }
        odp+=ile[zjd[0]]*ile[zjd[1]];
        if(!dol[zjd[2]].empty())
        {
            int najm=zjd[2]*pot3[k-gle-1];
            int najw=zjd[2];
            for(int i=1;i<k-gle;++i)
                najw=najw*3+2;
            int it_dol=0;
            for(int i=najm;i<=najw;++i)
            {
                if(it_dol<dol[zjd[2]].size())
                {
                    if(dol[zjd[2]][it_dol]==i)
                    {
                        ++it_dol;
                        continue;
                    }
                }
                vector<int>wtf=intdotroj(i,k-gle);
                for(auto j:dol[zjd[0]])
                {
                    if(istnieje[trzecia(intdotroj(j,k-gle),wtf)]==akt)
                        --odp;
                }
            }
        }
    }
    ++gle;
    wejdz(pocz,pocz+org_ile[0]-1,wek);
    wejdz(pocz+org_ile[0],pocz+org_ile[0]+org_ile[1]-1,wek);
    wejdz(pocz+org_ile[0]+org_ile[1],kon,wek);
    --gle;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin>>n>>k;
    pot3[0]=1;
    for(int i=1;i<=k;++i)
        pot3[i]=pot3[i-1]*3;
    vector<int>wek(n);
    char wcz;
    int doktej=1;
    for(int i=1;i<=k;++i)
        doktej*=3;
    for(int i=0;i<n;++i)
    {
        int wtroj=0;
        for(int j=0;j<k;++j)
        {
            cin>>wcz;
            wek[i]=wek[i]*3+wcz-'1';
        }
    }
    wejdz(0,n-1,wek);
    cout<<odp;
}

Compilation message (stderr)

Main.cpp: In function 'int trzecia(std::vector<int>, std::vector<int>)':
Main.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<p.size();++i)
      |                 ~^~~~~~~~~
Main.cpp: In function 'int trojdoint(std::vector<int>&)':
Main.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<a.size();++i)
      |                 ~^~~~~~~~~
Main.cpp: In function 'void wejdz(int, int, std::vector<int>&)':
Main.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             if(it_dol<dol[zjd[2]].size())
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             if(it_dol<dol[zjd[1]].size())
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:180:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |                 if(it_dol<dol[zjd[2]].size())
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:217:13: warning: unused variable 'wtroj' [-Wunused-variable]
  217 |         int wtroj=0;
      |             ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 70