Submission #933924

#	Time	Username	Problem	Language	Result	Execution time	Memory
933924		De3b0o	Virus Experiment (JOI19_virus)	C++14	6 / 100	2095 ms	9100 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 main()
{
    d3
    int m;
    int16_t r,c;
    string d;
    cin >> m >> r >> c;
    cin >> d;
    int a[r+1][c+1];
    int b[2][2][2][2];
    for(int16_t i = 1 ; r>=i ; i++)
        for(int16_t j = 1 ; c>=j ; j++)
        {
            cin >> a[i][j];
            if(a[i][j]==0)
                a[i][j]=1e5+1;
        }
    d+=d;
    for(int8_t 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);
        if(lon==2*m)
            lon=1e5;
        b[l1][l2][l3][l4]=lon;
        //cout << l1 << " " << l2 << " " << l3 << " " << l4 << " " << b[l1][l2][l3][l4] << "\n";
    }
    int mn = 1e6;
    int ans = 0;
    pair<int,int> A[r*c];
    for(int i = 1 ; r>=i ; i++)
        for(int j = 1 ; c>=j ; j++)
            A[(i-1)*c+j-1]={i,j};
    random_shuffle(A,A+r*c);
    bool infected[r+2][c+2];
    bool tak[r+1][c+1];
    memset(tak,0,sizeof(tak));
    for(int iiii = 0 ; r*c>iiii ; iiii++)
    {
        int16_t x = A[iiii].F;
        int16_t y = A[iiii].S;
        if(a[x][y]>1e5)
            continue;
        memset(infected,0,sizeof(infected));
        queue<pair<int16_t,int16_t>> q;
        q.push({x+1,y});
        q.push({x-1,y});
        q.push({x,y-1});
        q.push({x,y+1});
        infected[x][y]=1;
        bool ge = 0;
        int mn1 = 1;
        while(!q.empty())
        {
            pair<int16_t,int16_t> nod = q.front();
            q.pop();
            if(infected[nod.F][nod.S]||nod.F<1||nod.F>r||nod.S<1||nod.S>c)
                continue;
            if(mn1>mn)
                break;
            int16_t xx = nod.F , yy = nod.S;
            bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
            if(infected[xx+1][yy])
                l1=1;
            if(infected[xx-1][yy])
                l2=1;
            if(infected[xx][yy+1])
                l3=1;
            if(infected[xx][yy-1])
                l4=1;
            if(b[l1][l2][l3][l4]>=a[xx][yy])
            {
                if(tak[xx][yy])
                {
                    ge=1;
                    break;
                }
                mn1++;
                infected[xx][yy]=1;
                q.push({xx+1,yy});
                q.push({xx-1,yy});
                q.push({xx,yy-1});
                q.push({xx,yy+1});
            }
        }
        tak[x][y]=1;
        if(ge)
            continue;
        if(mn1==mn)
            ans++;
        if(mn1<mn)
        {
            ans=1;
            mn=mn1;
        }
    }
    cout << mn << "\n" << ans*mn;
}

Compilation message (stderr)

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

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