제출 #857417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857417		Tudy006	Squirrel (RMI18_squirrel)	C++14	100 / 100	3362 ms	1104 KiB

squirrel

#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 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 50 / 50