Submission #1005482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005482		De3b0o	Virus Experiment (JOI19_virus)	C++14	100 / 100	382 ms	21892 KiB

virus

#include<bits/stdc++.h>
#define F first
#define S second
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back

using namespace std;

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;
}

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;
    }
    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));
    memset(infected,0,sizeof(infected));
    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;
        vector<pair<int,int>> qwerty;
        queue<pair<int16_t,int16_t>> q;
        q.push({x,y});
        bool ge = 0;
        int mn1 = 0;
        while(!q.empty())
        {
            pair<int16_t,int16_t> nod = q.front();
            q.pop();
            if(infected[nod.F][nod.S])
                continue;
            qwerty.pb({nod.F,nod.S});
            infected[nod.F][nod.S]=1;
            mn1++;
            if(mn1>mn)
                break;
            for(int8_t ii = 0 ; 4>ii ; ii++)
            {
                int16_t xx = nod.F , yy = nod.S;
                if(ii==1)
                    xx++;
                else if(ii==2)
                    xx--;
                else if(ii==3)
                    yy++;
                else
                    yy--;
                if(xx<1||xx>r||yy<1||yy>c||infected[xx][yy])
                    continue;
                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;
                    }
                    q.push({xx,yy});
                }
            }
            if(ge)
                break;
        }
        tak[x][y]=1;
        for(auto it : qwerty)
            infected[it.F][it.S]=0;
        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:58:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         for(int j = 0 ; d.size()>j ; j++)
      |                         ~~~~~~~~^~

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