oj.uz

Submission #857448

# Submission time Handle Problem Language Result Execution time Memory
857448 2023-10-06T08:08:51 Z Tudy006 Squirrel (RMI18_squirrel) C++14
100 / 100
 3019 ms 1108 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 ) {
    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 ans = 0;
//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;
//}
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 += dirl[dir];
        c += dirc[dir];
        ans += isCoprime(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 += dirl[dir1];
        c1 += dirc[dir1];
        ans += isCoprime(l1, c1);
    }
//    cout << dir2 << " Branch 2 : " << endl;
    int l2 = l, c2 = c;
    for(int i = 0; i < size / 2; i++) {
        l2 += dirl[dir2];
        c2 += dirc[dir2];
        ans += isCoprime(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() {
    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 );
            }
        }
    }
    for ( int i = 1, l, c, p; i <= f; i ++ ) {
        cin >> l >> c >> p;
        ans += isCoprime( l - 1, c - 1 );
        generateFractal( l - 1, c - 1, 0, p );
    }
    cout << ans << '\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 11 ms 856 KB Output is correct
2 Correct 21 ms 860 KB Output is correct
3 Correct 404 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 1036 KB Output is correct
2 Correct 652 ms 860 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 1020 KB Output is correct
2 Correct 1100 ms 1108 KB Output is correct
3 Correct 1150 ms 1024 KB Output is correct
4 Correct 1203 ms 1016 KB Output is correct
5 Correct 1250 ms 1108 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2212 ms 1020 KB Output is correct
2 Correct 2352 ms 1020 KB Output is correct
3 Correct 2460 ms 1020 KB Output is correct
4 Correct 2594 ms 1020 KB Output is correct
5 Correct 2722 ms 856 KB Output is correct
6 Correct 2856 ms 1020 KB Output is correct
7 Correct 2986 ms 1028 KB Output is correct
8 Correct 3019 ms 1020 KB Output is correct
9 Correct 2986 ms 860 KB Output is correct
10 Correct 2976 ms 1104 KB Output is correct