oj.uz

Submission #857417

# Submission time Handle Problem Language Result Execution time Memory
857417 2023-10-06T07:26:12 Z Tudy006 Squirrel (RMI18_squirrel) C++14
100 / 100
 3362 ms 1104 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5e4;

long long primes[NMAX + 1];
int maxPrime[NMAX + 1];

bool isCoprime( int a, int b ) {
//    cout << a + 1 << ' ' << b + 1 << endl;
    if ( a == 1 || b == 1 ) return true;
    if ( a == 0 || b == 0 ) return false;
    if ( ( primes[a] & primes[b] ) || ( maxPrime[a] == maxPrime[b] ) ) return false;
    return true;
}

int dirl[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dirc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int scad( int x ) {
    return x == 0 ? 7 : x - 1;
}
int add( int x ) {
    return x == 7 ? 0 : x + 1;
}
int generateFractal( int l, int c, int dir, int siz ) {
    if ( siz == 0 ) return 0;
//    cout << "The Start is: " << l + 1 << ' ' << c + 1 << endl;
    int cnt = 0;
    for ( int i = 1; i <= siz; i ++ ) {
        cnt += isCoprime( l + i * dirl[dir], c + i * dirc[dir] );
    }
    int st = scad( dir ), dr = add( dir );

    l += siz * dirl[dir];
    c += siz * dirc[dir];
    for ( int i = 1; i <= siz / 2; i ++ ) {
        cnt += isCoprime( l + dirl[st] * i, c + dirc[st] * i );
        cnt += isCoprime( l + dirl[dr] * i, c + dirc[dr] * i );
    }
    cnt += generateFractal( l + dirl[st] * siz / 2, c + dirc[st] * siz / 2, dir, siz / 2 );
    cnt += generateFractal( l + dirl[st] * siz / 2, c + dirc[st] * siz / 2, scad( st ), siz / 2 );

    cnt += generateFractal( l + dirl[dr] * siz / 2, c + dirc[dr] * siz / 2, dir, siz / 2 );
    cnt += generateFractal( l + dirl[dr] * siz / 2, c + dirc[dr] * siz / 2, add( dr ), siz / 2 );
    return cnt;
}

//bool brut( int i, int j ) {
//    return ( __gcd( i, j ) == 1 );
//}
int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    cout.tie( NULL );
    int n, m, f;
    cin >> n >> m >> f;
    for ( int i = 2; i <= NMAX; i ++ ) {
        if ( maxPrime[i] == 0 ) {
            for ( int j = i; j <= NMAX; j += i ) {
                maxPrime[j] = i;
            }
        }
    }
    int cnt = -1;
    for ( int i = 2; i * i <= NMAX; i ++ ) {
        if ( primes[i] == 0 ) {
            cnt ++;
            for ( int j = i; j <= NMAX; j += i ) {
                primes[j] ^= ( 1LL << cnt );
            }
        }
    }
    int answer = 0;
    for ( int i = 1, l, c, p; i <= f; i ++ ) {
        cin >> l >> c >> p;
//        cout << endl;
//        cout << generateFractal( l - 1, c - 1, 0, p ) + isCoprime( l - 1, c - 1 ) << endl;
        answer += generateFractal( l - 1, c - 1, 0, p ) + isCoprime( l - 1, c - 1 );
    }
    cout << answer << '\n';
    return 0;
}

/**
14 20 1
7 6 2
11 10 4
8 7 2
**/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 860 KB Output is correct
2 Correct 24 ms 860 KB Output is correct
3 Correct 456 ms 1104 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 1028 KB Output is correct
2 Correct 727 ms 1024 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 1036 KB Output is correct
2 Correct 1240 ms 1024 KB Output is correct
3 Correct 1302 ms 1020 KB Output is correct
4 Correct 1329 ms 1024 KB Output is correct
5 Correct 1405 ms 1028 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2489 ms 1032 KB Output is correct
2 Correct 2634 ms 1028 KB Output is correct
3 Correct 2780 ms 1024 KB Output is correct
4 Correct 2899 ms 1040 KB Output is correct
5 Correct 3070 ms 1032 KB Output is correct
6 Correct 3288 ms 1028 KB Output is correct
7 Correct 3350 ms 1036 KB Output is correct
8 Correct 3362 ms 1028 KB Output is correct
9 Correct 3338 ms 1028 KB Output is correct
10 Correct 3343 ms 1036 KB Output is correct