Submission #697183

#	Time	Username	Problem	Language	Result	Execution time	Memory
697183		bin9638	Raspad (COI17_raspad)	C++17	61 / 100	6031 ms	43508 KiB

raspad

#include<bits/stdc++.h>

using namespace std;
#define N  100010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("omit-frame-pointer")
#pragma GCC optimize("unroll-loops")

int f[N],a[N][55],n,m;

struct haha
{
    int val=0,sum=0,sl=0;
    int32_t cnt[52]={},id[52]={},ktr[52]={};

    int get(int mod)
    {
        int res=0;
        for(int i=1;i<=m;i++)
            res=(res+f[i]%mod*id[i])%mod;
        return res;
    }

    void DFS(int u,int dem,int h)
    {
        ktr[u]=dem;
        if(ktr[u-1]==0&&a[h][u-1]==1)
            DFS(u-1,dem,h);
        if(ktr[u+1]==0&&a[h][u+1]==1)
            DFS(u+1,dem,h);
        for(int i=1;i<=m;i++)
            if(ktr[i]==0&&id[i]==id[u])
                DFS(i,dem,h);
    }

    void build(int h)
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=m;i++)
            if(id[i]!=0)
                cnt[id[i]]=1;
        int dem=m+1;
        for(int i=1;i<=m;i++)
            if(a[h][i]==0)
                id[i]=0;
                else{
                    if(id[i]==0)
                        id[i]=++dem;
                }
        for(int i=1;i<=m;i++)
            if(id[i]!=0&&id[i]<=m)
                cnt[id[i]]=0;
        for(int i=1;i<=m;i++)
            if(cnt[i]>0)
                sum+=sl;
        dem=0;
        memset(ktr,0,sizeof(ktr));
        for(int i=1;i<=m;i++)
            if(ktr[i]==0&&id[i]!=0)
            {
                dem++;
                DFS(i,dem,h);
            }
        for(int i=1;i<=m;i++)
            id[i]=ktr[i];
        val=get(1e9+8277);
    }

    int solve()
    {
        memset(cnt,0,sizeof(cnt));
         for(int i=1;i<=m;i++)
            if(id[i]!=0)
                cnt[id[i]]=1;
        int res=0;
        for(int i=1;i<=m;i++)
            if(cnt[i]!=0)
                res++;
        return res;
    }

};
vector<haha>s,luu,vec;
vector<ii>SS;

int32_t main()
{
  //  freopen("A.inp","r",stdin);
 //   freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        s=" "+s;
        for(int j=1;j<=m;j++)
        {
           // a[i][j]=rand()%2;
            a[i][j]=(s[j]-'0');
          ///  cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
        }
    }
    for(int i=1;i<=m;i++)
        f[i]=1ll*rand()*rand()*rand();
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        s.emplace_back();
        s.back().sl=1;
        for(int j=0;j<s.size();j++)
            s[j].build(i);
        SS.clear();
        for(int j=0;j<s.size();j++)
            SS.pb({s[j].val,j});
        sort(SS.begin(),SS.end());
        vec.clear();
        for(int j=0;j<s.size();j++)
             vec.pb(s[SS[j].sc]);
        s=vec;
        luu.clear();
        while(!s.empty())
        {
            haha cc=s.back();
            s.pop_back();
            if(!s.empty()&&s.back().val==cc.val)
            {
                s.back().sum+=cc.sum;
                s.back().sl+=cc.sl;
            }else
            {
                luu.pb(cc);
            }
        }
        s=luu;
        for(auto cc:s)
            ans+=cc.sum+cc.solve()*cc.sl;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int32_t main()':
raspad.cpp:122:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<haha>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~
raspad.cpp:125:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<haha>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~
raspad.cpp:129:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<haha>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 0 / 39