Submission #805664

#	Time	Username	Problem	Language	Result	Execution time	Memory
805664		Augustyn	Set (COCI21_set)	C++17	40 / 110	1068 ms	99252 KiB

Main

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

int n,k,odp=0,akt;
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<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][i]-1];
        }
        sort(ile,ile+3);
        long long op=min(ile[0]*ile[1],(pot3[k-gle-1]-ile[2])*ile[0]);
        if(op<op_naj)
        {
            op_naj=op;
            najlep=i;
        }
    }
    ile[0]=ile[1]=ile[2]=0;
    vector<vector<int>>dol[3];
    for(int i=pocz;i<=kon;++i)
    {
        swap(wek[i][gle],wek[i][najlep]);
        ++ile[wek[i][gle]-1];
        vector<int>wrzuc;
        for(int j=gle;j<k;++j)
        {
            wrzuc.push_back(wek[i][j]);
        }
        dol[wek[i][gle]-1].push_back(wrzuc);
    }
    sort(wek.begin()+pocz,wek.begin()+kon+1);
    
    //tutaj licze odp dla tego gowna
    int org_ile[3];
    for(int i=0;i<3;++i)
        org_ile[i]=ile[i];

    if(ile[0]>ile[1])
    {
        swap(ile[0],ile[1]);
        swap(dol[0],dol[1]);
    }
    if(ile[1]>ile[2])
    {
        swap(ile[1],ile[2]);
        swap(dol[1],dol[2]);
    }
    if(ile[0]>ile[1])
    {
        swap(ile[0],ile[1]);
        swap(dol[0],dol[1]);
    }

    ++akt;
   // cout<<"MOzetu "<<gle<<" "<<ile[0]<<" "<<ile[1]<<" "<<ile[2]<<" "<<pot3[k-gle-1]<<endl;
    if(1/*ile[1]<pot3[k-gle-1]-ile[2]*/)
    {
       // cout<<'a'<<endl;
        //wszyskie z ile[0]xile[1]
        for(auto i:dol[2])
        {
            int dowrz_ist=0;
            for(auto j:i)
                dowrz_ist=dowrz_ist*3+j-1;
            istnieje[dowrz_ist]=akt;
        }
        for(auto i:dol[0])
            for(auto j:dol[1])
                if(istnieje[trzecia(i,j)]==akt)
                    ++odp;
    }
    else
    {
        //cout<<'b'<<endl;
        //wszystkie z ile[0]xbrakujace z ile[2]
        for(auto i:dol[1])
        {
            int dowrz_ist=0;
            for(auto j:i)
                dowrz_ist=dowrz_ist*3+j-1;
            istnieje[dowrz_ist]=akt;
            // if(gle==0)
            // cout<<"kurwa"<<dowrz_ist<<endl;
        }
        odp+=ile[0]*ile[1];
        if(!dol[2][0].empty())
        {
            int najm=(dol[2][0][0]-1)*pot3[dol[2][0].size()-1];
            int najw=dol[2][0][0]-1;
            for(int i=1;i<dol[2][0].size();++i)
                najw=najw*3+2;
            int it_dol=0;
            for(int i=najm;i<=najw;++i)
            {
                if(it_dol<dol[2].size())
                {
                    if(trojdoint(dol[2][it_dol])==i)
                    {
                        ++it_dol;
                        continue;
                    }
                }
                vector<int>wtf=intdotroj(i,k-gle);
                for(auto j:dol[0])
                {
                    // if(gle==2)
                    // {
                    //     cout<<"mac"<<trzecia(j,wtf)<<" ";
                    //     for(auto xd:j)
                    //     cout<<xd;
                    //     cout<<" ";
                    //     for(auto wtt:wtf)
                    //         cout<<wtt;
                    //         cout<<endl;
                    // }
                    if(istnieje[trzecia(j,wtf)]==akt)
                        --odp;
                }
            }
        }
    }
    //cout<<gle<<" "<<odp<<endl;
    // if(gle==3)
    // {
    //     for(int i=pocz;i<=kon;++i)
    //     {
    //         for(auto j:wek[i])
    //         cout<<j;
    //         cout<<endl;
    //     }
    //     cout<<endl;
    // }
    ++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<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)
    {
        wek[i].resize(k);
        int wtroj=0;
        for(int j=0;j<k;++j)
        {
            cin>>wcz;
            wek[i][j]=wcz-'0';
        }
    }
    wejdz(0,n-1,wek);
    cout<<odp;
}

Compilation message (stderr)

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

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