oj.uz

Submission #857433

# Submission time Handle Problem Language Result Execution time Memory
857433 2023-10-06T07:58:38 Z lbadea1000 Squirrel (RMI18_squirrel) C++17
100 / 100
 4062 ms 12888 KB 
#include <bits/stdc++.h>

using namespace std;

int ldir[8] = {-1, -1, 0, 1, 1,  1,  0, -1};
int cdir[8] = { 0,  1, 1, 1, 0, -1, -1, -1};

int ans;

const int NMAX = 1e4;

bitset<NMAX> isCoprime[NMAX]; // isc[i][j] = gcd(i, j)


bool gcd(int a, int b) {
//    cout << a + 1 << ' ' << b + 1 << endl;
    if(a < b) swap(a, b);
    while(a >= NMAX) {
        if(b == 0)
            return false;
        int r = a % b;
        a = b;
        b = r;
    }
    return isCoprime[a][b];
}

void generateFractal(int l, int c, int dir, int size) {
    if(size == 0)
        return;
    //cout << "tree : " << endl;
    for(int i = 0; i < size; i++) {
        l += ldir[dir];
        c += cdir[dir];
        ans += gcd(l, c);
    }
    //cout << endl;
    int dir1 = (dir - 1 + 8) % 8, dir2 = (dir + 1) % 8;
    int l1 = l, c1 = c;
    //cout << dir1 << " Branch 1 : " << endl;
    for(int i = 0; i < size / 2; i++) {
        l1 += ldir[dir1];
        c1 += cdir[dir1];
        ans += gcd(l1, c1);
    }
//    cout << dir2 << " Branch 2 : " << endl;
    int l2 = l, c2 = c;
    for(int i = 0; i < size / 2; i++) {
        l2 += ldir[dir2];
        c2 += cdir[dir2];
        ans += gcd(l2, c2);
    }
//    cout << endl << endl;
    generateFractal(l1, c1, (dir1 - 1 + 8) % 8, size / 2);
    generateFractal(l1, c1, (dir1 + 1 + 8) % 8, size / 2);
    generateFractal(l2, c2, (dir2 - 1 + 8) % 8, size / 2);
    generateFractal(l2, c2, (dir2 + 1 + 8) % 8, size / 2);
}

int main() {
    int m, n, f;
    cin >> m >> n >> f;
    ans = 0;
    for(int i = 0; i < NMAX; i++)
        isCoprime[0][i] = 0, isCoprime[i][0] = 0;
    isCoprime[0][1] = isCoprime[1][0] = 1;
    for(int i = 1; i < NMAX; i++) {
        for(int j = 1; j <= i; j++) {
            if ( i - j < j ) {
                isCoprime[i][j] = isCoprime[j][i - j];
            } else {
                isCoprime[i][j] = isCoprime[i - j][j];
            }
        }
    }
    for(int i = 0; i < f; i++) {
        int l, c, size;
        cin >> l >> c >> size;
        l--;
        c--;
        ans += gcd(l, c);
        generateFractal(l, c, 0, size);
    }
    cout << ans;
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 12700 KB Output is correct
2 Correct 154 ms 12632 KB Output is correct
3 Correct 632 ms 12712 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 12700 KB Output is correct
2 Correct 913 ms 12700 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1425 ms 12700 KB Output is correct
2 Correct 1453 ms 12696 KB Output is correct
3 Correct 1600 ms 12700 KB Output is correct
4 Correct 1519 ms 12704 KB Output is correct
5 Correct 1723 ms 12704 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2972 ms 12700 KB Output is correct
2 Correct 3091 ms 12700 KB Output is correct
3 Correct 3396 ms 12700 KB Output is correct
4 Correct 3404 ms 12696 KB Output is correct
5 Correct 3678 ms 12700 KB Output is correct
6 Correct 3674 ms 12700 KB Output is correct
7 Correct 3929 ms 12704 KB Output is correct
8 Correct 4062 ms 12888 KB Output is correct
9 Correct 3850 ms 12700 KB Output is correct
10 Correct 3940 ms 12700 KB Output is correct