oj.uz

답안 #805670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805670 2023-08-03T19:57:03 Z Augustyn Set (COCI21_set) C++17
40 / 110
 1000 ms 115484 KB 
#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];
    }
    sort(wek.begin()+pocz,wek.begin()+kon+1);
    for(int i=pocz;i<=kon;++i)
    {
        vector<int>wrzuc;
        for(int j=gle;j<k;++j)
        {
            wrzuc.push_back(wek[i][j]);
        }
        dol[wek[i][gle]-1].push_back(wrzuc);
    }
    //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;
    if(ile[1]<pot3[k-gle-1]-ile[2])
    {
        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
    {
        //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;
        }
        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(istnieje[trzecia(j,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<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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 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 1 ms 212 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 5 ms 596 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 5 ms 676 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 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 1 ms 212 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 5 ms 596 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 5 ms 676 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 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 Execution timed out 1088 ms 115484 KB Time limit exceeded
35 Halted 0 ms 0 KB -