Submission #933260

#	Time	Username	Problem	Language	Result	Execution time	Memory
933260		De3b0o	Virus Experiment (JOI19_virus)	C++14	0 / 100	232 ms	7092 KiB

virus

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z*x;
    else
        return z*z;
}

int sqrot(ll x)
{
    int l = 0 , r = INT_MAX;
    while(l<=r)
    {
        if(mid*mid>=x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r+1;
}

ll cel(ll x , ll y)
{
    return x/y + bool(x/y);
}

string tb(ll x)
{
    string s = "";
    while(x>0)
    {
        if(x&1)
            s+='1';
        else
            s+='0';
        x/=2;
    }
    while(s.size()<4)
        s+='0';
    return s;
}

ll fb(string s)
{
    ll x = 0;
    ll c = 1;
    for(int8_t i = 0 ; 60>i ; i++)
    {
        if(s[i]=='1')
            x+=c;
        c*=2;
    }
    return x;
}

int m , r , c;
string d;
int a[809][809];
int b[2][2][2][2];

int bfs(int i , int j)
{
    queue<pair<int,int>> q;
    q.push({i+1,j});
    q.push({i-1,j});
    q.push({i,j-1});
    q.push({i,j+1});
    bool infected[r+2][c+2];
    memset(infected,0,sizeof(infected));
    infected[i][j]=1;
    while(!q.empty())
    {
        auto x = q.front();
        q.pop();
        int i1 = x.F;
        int j1 = x.S;
        if(infected[i1][j1]||i1<1||j1<1||i1>r||j1>c||a[i1][j1]==0)
            continue;
        bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
        if(infected[i1+1][j1])
            l1=1;
        if(infected[i1-1][j1])
            l2=1;
        if(infected[i1][j1+1])
            l3=1;
        if(infected[i1][j1-1])
            l4=1;
        if(b[l1][l2][l3][l4]>=a[i1][j1])
        {
            infected[i1][j1]=1;
            q.push({i1+1,j1});
            q.push({i1-1,j1});
            q.push({i1,j1+1});
            q.push({i1,j1-1});
        }
    }
    int an = 0;
    for(int i2 = 1 ; r>=i2 ; i2++)
        for(int j2 = 1 ; c>=j2 ; j2++)
            if(infected[i2][j2])
                an++;
    return an;
}

int main()
{
    d3
    cin >> m >> r >> c;
    cin >> d;
    for(int i = 1 ; r>=i ; i++)
        for(int j = 1 ; c>=j ; j++)
            cin >> a[i][j];
    while(d.size()<=200000)
        d+=d;
    for(int i = 1 ; 16>=i ; i++)
    {
        string s = tb(i);
        bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
        if(s[0]=='1')
            l1=1;
        if(s[1]=='1')
            l2=1;
        if(s[2]=='1')
            l3=1;
        if(s[3]=='1')
            l4=1;
        int lon = 0;
        int cur = 0;
        for(int j = 0 ; d.size()>j ; j++)
        {
            if((d[j]=='S'&&l1)||(d[j]=='N'&&l2)||(d[j]=='E'&&l3)||(d[j]=='W'&&l4))
            {
                cur++;
                continue;
            }
            lon=max(lon,cur);
            cur=0;
        }
        lon=max(lon,cur);
        b[l1][l2][l3][l4]=lon;
        //cout << l1 << " " << l2 << " " << l3 << " " << l4 << " " << b[l1][l2][l3][l4] << "\n";
    }
    bool g = 1;
    for(int i = 0 ; m>i ; i++)
    {
        if(d[i]=='N'||d[i]=='S')
            g=0;
    }
    if(g)
    {
        int mn = 1e8;
        int ans = 0;
        for(int i = 1 ; r>=i ; i++)
        {
            for(int j = 1 ; c>=j ; j++)
            {
                if(a[i][j]==0)
                    continue;
                int ans1 = 1;
                for(int h = j-1 ; h>0 ; h--)
                {
                    if(b[0][0][1][0]>=a[i][h])
                    {
                        ans1++;
                        continue;
                    }
                    break;
                }
                for(int h = j+1 ; c>=h ; h++)
                {
                    if(b[0][0][0][1]>=a[i][h])
                    {
                        ans1++;
                        continue;
                    }
                    break;
                }
                if(ans1==mn)
                    ans++;
                else if(ans1<mn)
                {
                    mn=ans1;
                    ans=1;
                }
            }
        }
        cout << mn << "\n" << ans;
        return 0;
    }
    int mn = 1e8;
    int ans = 0;
    for(int i = 1 ; r>=i ; i++)
    {
        for(int j = 1 ; c>=j ; j++)
        {
            if(a[i][j]==0)
                continue;
            int mn1 = bfs(i,j);
            if(mn==mn1)
                ans++;
            if(mn>mn1)
            {
                ans=1;
                mn=mn1;
                //cout << mn << " " << i << " " << j << "\n";
            }
        }
    }
    cout << mn << "\n" << ans;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:156:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  156 |         for(int j = 0 ; d.size()>j ; j++)
      |                         ~~~~~~~~^~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80