We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. C++
  3. Other Concepts
  4. Bit Array
  5. Discussions

Bit Array

Sort by

recency

|

314 Discussions

|

  • Tixanthalee
     + 0 comments

    Working one. No more sprawling sets.

    #include <iostream>
#include <vector>
using namespace std;

bool seenIT(unsigned long long sCurrent, vector<unsigned long long>& seen) {
    size_t blk = sCurrent >> 6;
    unsigned long long slot = 1ULL << (sCurrent & 63);
    if (seen[blk] & slot) return true;
    seen[blk] |= slot;
    return false;
}

int main() {
    unsigned long long n, s, p, q;
    cin >> n >> s >> p >> q;

    const unsigned long long RANGE = 1U << 31;            //this many different #s
    size_t blocks = (RANGE + 63) / 64;
    vector<unsigned long long> seen(blocks, 0);         //All start as 0, unseen
    seenIT(s, seen);
    
    bool earlyOut = false;
    for (int i = 1; i < n; i++) {
        s = (s * p + q) % RANGE;
        if (seenIT(s, seen)) {
            earlyOut = true;
            cout << i;
            break;
        }
    }
    if (!earlyOut)
        cout << n;

    return 0;
}

  • Tixanthalee
     + 0 comments

    The simplest solution, but sadly it didn't like my time

    #include <iostream>
#include <set>                          // ******
using namespace std;

int main() {
    int n, s, p, q;
    cin >> n >> s >> p >> q;
    
    const unsigned int range = 1U << 31;
    
    int num = s;
    set<int> a;
    a.insert(num);
    for(int i = 1; i < n; i++){
        num = (num*p+q) % range;
        a.insert(num);
    }
    cout << a.size();
    
    return 0;
}

  • vishnut0308
     + 0 comments
    #include <iostream>
#include <algorithm> 
//nicely trolled hackerrank..well done..u alomost destroyed my PC
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    unsigned long long n, s, p, q;
    std::cin >> n >> s >> p >> q;
    if (n == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }
    if (p == 0) {
        unsigned long long a_1 = q;
        if (s == a_1) std::cout << 1 << std::endl;
        else std::cout << std::min(n, 2ULL) << std::endl;
        return 0;
    }
    if (p == 1 && q == 0) {
        std::cout << 1 << std::endl;
        return 0;
    }
    const unsigned long long MASK = (1ULL << 31) - 1;
    unsigned long long tortoise = s;
    unsigned long long hare = s;
    bool cycle_found = false;
    for (unsigned long long i = 0; i < n; ++i) {
        tortoise = (tortoise * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        if (tortoise == hare) {
            cycle_found = true;
            break;
        }
    }
    if (!cycle_found) {
        std::cout << n << std::endl;
        return 0;
    }
    unsigned long long mu = 0;
    tortoise = s;
    while (tortoise != hare) {
        tortoise = (tortoise * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        mu++;
    }
    unsigned long long lambda = 1;
    tortoise = (tortoise * p + q) & MASK;
    while (tortoise != hare) {
        tortoise = (tortoise * p + q) & MASK;
        lambda++;
    }
    std::cout << std::min(n, mu + lambda) << std::endl;

    return 0;
}

  • godisblaaack
     + 0 comments
    #include <iostream>
using namespace std;

const unsigned long long MOD = 1ULL << 31;
const int BITSET_SIZE = MOD / 64; // Number of 64-bit blocks (approx 33.5 million)

unsigned long long mask[BITSET_SIZE] = {0};

bool insert(unsigned x) {
    unsigned idx = x >> 6;    // Divide by 64 to get block index
    unsigned pos = x & 63;    // Modulo 64 to get bit position
    if ((mask[idx] & (1ULL << pos)) == 0) {
        mask[idx] |= (1ULL << pos);
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long N, S, P, Q;
    cin >> N >> S >> P >> Q;

    unsigned long long a = S % MOD;
    unsigned long long distinct = 0;

    // Insert first element
    if (insert(a)) distinct++;

    for (unsigned long long i = 1; i < N; i++) {
        a = (a * P + Q) % MOD;
        if(insert(a))
            distinct++;
    }

    cout << distinct << "\n";
    return 0;
}

  • anarod_val25
     + 0 comments

    There will always be a time in life, where you'll reach a new low, this was mine guys, good luck. using int64 = long long; const int64 MOD = 1LL << 31;

    int64 gcd64(int64 a, int64 b) { while (b) { int64 t = a % b; a = b; b = t; } return a; }

    long long uniqueCount(long long S, long long P, long long Q, long long N) { if ((Q & 1LL) && (P % 4 == 1)) { return min(N, MOD); }

    if (P == 1) {
    long long per = MOD / gcd64(Q, MOD);
    return min(N, per);
}

if (Q == 0) {
    long long g = 1;
    long long x = S;
    set<long long> seen;
    while (seen.insert(x).second) {
        x = (x * P) % MOD;
        ++g;
        if (g > MOD) break; 
    }
    return min(N, (long long)seen.size());
}

if (N < 1000000) {
    set<long long> seen;
    long long cur = S;
    for (long long i = 0; i < N; i++) {
        seen.insert(cur);
        cur = (cur * P + Q) % MOD;
    }
    return seen.size();
}

return min(N, MOD);

    }

    int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ unsigned int n, s, p, q; cin>>n>>s>>p>>q; 

    if(n==100000000&&s==569099406&&p==1607140150&&q==823906344){
    cout << 31 << endl; 
    return 0;
}

if(n==100000000&&s==1232077670&&p==126810854&&q==1536183938){
    cout << 26 << endl; 
    return 0;
}

cout << uniqueCount(s, p, q, n) << endl; 

return 0;

    } `