Submission #3227670


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

const long long MaxN = 5e2 + 17;
long long arr[MaxN][MaxN];
long long prime[4 * MaxN];
long long second_matrix[MaxN][MaxN];
int x[] = {-1, 1, 0, 0};
int y[] = {0, 0, -1, 1};
int n = 505;
map<long long, bool> mp;

long long lcm(long long a, long long b)
{
    return (a * b) / __gcd(a, b);
}

void erich()
{
    const int MaxS = 2e4 + 17;
    bool isPrime[MaxS];

    for(int i = 2; i < MaxS; ++i)
        isPrime[i] = 1;

    int next = 1;

    for(int i = 2; i < MaxS; ++i)
    {
        if(isPrime[i])
        {
            prime[next++] = i;

            for(int j = i + i; j < MaxS; j += i)
                isPrime[j] = 0;

        }
    }
}

void fill_sec()
{
    for(int i = n - !(n % 2), j = 1; i >= 1; i -= 2, ++j)
    {
        int x = i;
        int y = 1;

        while(x <= n && y <= n)
        {
            second_matrix[x][y] = prime[n + j];
            ++x;
            ++y;
        }
    }

    for(int i = 3, j = 1; i <= n; i += 2, ++j)
    {
        int x = 1;
        int y = i;

        while(x <= n && y <= n)
        {
            second_matrix[x][y] = prime[n + n / 2 +  n % 2 + j];
            ++x;
            ++y;
        }
    }
}

void fill_matrix()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(!((i + j) & 1))
                arr[i][j] = prime[(i + j) / 2] * second_matrix[i][j];

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if((i + j) & 1)
            {
                arr[i][j] = 1;

                for(int k = 0; k < 4; ++k)
                {
                    int xx = i + x[k];
                    int yy = j + y[k];

                    if(xx >= 1 && xx <= n && yy >= 1 && yy <= n)
                        arr[i][j] = lcm(arr[i][j], arr[xx][yy]);
                }

                ++arr[i][j];
            }

}
bool check(long long a, long long b)
{
    return max(a, b) % min(a, b) == 1;
}
bool check()
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int k = 0; k < 4; ++k)
            {
                int xx = i + x[k];
                int yy = j + y[k];

                //if(xx >= 1 && xx <= n && yy >= 1 && yy <= n)
            }
        }
    }

    return true;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    erich();
    fill_sec();
    fill_matrix();

    int m;
    cin >> m;

    for(int i = 1; i <= m; ++i)
    {
        for(int j = 1; j <= m; ++j)
            cout << arr[i][j] << ' ';
        cout << '\n';
    }



}

Submission Info

Submission Time
Task D - Modulo Matrix
User burstintotears
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2721 Byte
Status
Exec Time 83 ms
Memory 7936 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt
All 0 / 1100 sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt
Case Name Status Exec Time Memory
sample_01.txt 60 ms 4480 KB
test_01.txt 83 ms 7936 KB
test_02.txt 83 ms 7808 KB
test_03.txt 60 ms 4480 KB
test_04.txt 60 ms 4480 KB
test_05.txt 60 ms 4480 KB
test_06.txt 72 ms 6144 KB
test_07.txt 61 ms 4608 KB