oj.uz

Submission #476055

# Submission time Handle Problem Language Result Execution time Memory
476055 2021-09-24T16:49:38 Z stefantaga Squirrel (RMI18_squirrel) C++14
100 / 100
 2774 ms 884 KB 
#include <bits/stdc++.h>

using namespace std;

long long bitmask[50005];
int mmare[50005];
int dl[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool prime(int x,int y)
{
    if (x==1||y==1)
    {
        return true;
    }
    if (x==0||y==0)
    {
        return false;
    }
    if (bitmask[x] & bitmask[y])
    {
        return false;
    }
    if (mmare[x]>1&&mmare[x]==mmare[y])
    {
        return false;
    }
    return true;
}
long long sum=0;
void fractal(int x,int y,int lung,int dir,int jum)
{
    if (lung==0)
    {
        return;
    }
    int i;
    for (i=1; i<=lung; i++)
    {
        x=x+dl[dir];
        y=y+dc[dir];
        sum=sum+prime(x,y);
    }
    if (jum)
    {
        lung=lung/2;
    }
    fractal(x,y,lung,(dir+1)&7,!jum);
    fractal(x,y,lung,(dir-1)&7,!jum);
}
bool c[50005];
int n,m,frac,i,j,nr,x,y,numar;
int main()
{
    cin>>n>>m>>frac;
    nr=-1;
    int lim=max(n,m);
    for (i=2; i<=lim; i++)
    {
        if (mmare[i]==0)
        {
            for (j=i; j<=lim; j+=i)
            {
                mmare[j]=i;
            }
        }
    }
    for (i=2; i*i<=lim; i++)
    {
        if (bitmask[i]==0)
        {
            nr++;
            for (j=i; j<=lim; j+=i)
            {
                bitmask[j]+=(1LL<<nr);
            }
        }
    }
    for (int i=1; i<=frac; i++)
    {
        cin>>x>>y>>numar;
        x--;
        y--;
        sum=sum+prime(x,y);
        fractal(x,y,numar,0,1);
    }
    cout<<sum<<'\n';
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is correct
2 Correct 19 ms 416 KB Output is correct
3 Correct 373 ms 860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 884 KB Output is correct
2 Correct 590 ms 864 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 990 ms 864 KB Output is correct
2 Correct 1006 ms 864 KB Output is correct
3 Correct 1058 ms 860 KB Output is correct
4 Correct 1095 ms 864 KB Output is correct
5 Correct 1155 ms 864 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2019 ms 864 KB Output is correct
2 Correct 2228 ms 860 KB Output is correct
3 Correct 2260 ms 860 KB Output is correct
4 Correct 2382 ms 860 KB Output is correct
5 Correct 2523 ms 864 KB Output is correct
6 Correct 2607 ms 864 KB Output is correct
7 Correct 2774 ms 868 KB Output is correct
8 Correct 2768 ms 868 KB Output is correct
9 Correct 2765 ms 864 KB Output is correct
10 Correct 2736 ms 860 KB Output is correct