Submission #933260

# Submission time Handle Problem Language Result Execution time Memory
933260 2024-02-25T10:35:55 Z De3b0o Virus Experiment (JOI19_virus) C++14
0 / 100
232 ms 7092 KB
#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

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++)
      |                         ~~~~~~~~^~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 41 ms 4524 KB Output is correct
3 Correct 232 ms 6936 KB Output is correct
4 Correct 192 ms 4696 KB Output is correct
5 Incorrect 62 ms 7092 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 1044 KB Output is correct
2 Correct 8 ms 1280 KB Output is correct
3 Correct 42 ms 1280 KB Output is correct
4 Incorrect 7 ms 1280 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 41 ms 4524 KB Output is correct
3 Correct 232 ms 6936 KB Output is correct
4 Correct 192 ms 4696 KB Output is correct
5 Incorrect 62 ms 7092 KB Output isn't correct
6 Halted 0 ms 0 KB -