oj.uz

Submission #805684

# Submission time Handle Problem Language Result Execution time Memory
805684 2023-08-03T20:22:22 Z Augustyn Set (COCI21_set) C++17
40 / 110
 1000 ms 10976 KB 
#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]);
        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[0]<<" "<<ile[1]<<" "<<ile[2]<<" "<<pot3[k-gle-1]-ile[2]<<endl;
    if(ile[zjd[1]]<pot3[k-gle-1]-ile[zjd[2]])
    {
        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

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:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 if(it_dol<dol[zjd[2]].size())
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:166:13: warning: unused variable 'wtroj' [-Wunused-variable]
  166 |         int wtroj=0;
      |             ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 8 ms 356 KB Output is correct
24 Correct 9 ms 340 KB Output is correct
25 Correct 9 ms 356 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 10 ms 340 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 8 ms 356 KB Output is correct
24 Correct 9 ms 340 KB Output is correct
25 Correct 9 ms 356 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 10 ms 340 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 606 ms 6748 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 324 KB Output is correct
38 Execution timed out 1080 ms 10976 KB Time limit exceeded
39 Halted 0 ms 0 KB -