#include <iostream>
#include <string>
#include <vector>

using namespace std;

// an array of bitmap uint64_t.

// bit 0 of bitmap[0] represents page 0.
// bit 0 of bitmap[1] represents page 64.

// array size 4096

// 1 - page is marked for use
// 0 - page is available for use

// Allocation()
// input: bitmap, size, n
// n contiguous pages
// returns: index of the first page of the allocation

// 0010001110010

// n=3. Result: page no. 3
// n=4. Result: -1
// n=2. Result: 0


// n = 80

#define BITMAP_SIZE 4096
#define BIT_SIZE 64


class Solution {

    vector<uint64_t> bitmap(BITMAP_SIZE, 0);
public:
    int alloc(int reqrd_pages) {
        int matches = 0;
        int start = -1;
        for (int i = 0; i < BITMAP_SIZE; i++) { // bitmap[0] = 0010001110010 j =
            for (int j = 0; j < BIT_SIZE; j++) {
                if(bitmap[i] >> j) & 0x1)
                    continue;
                if (start < 0)
                    start = j;
                while (j < BIT_SIZE && !((bitmap[i] >> j) & 0x1) && matches < reqrd_pages) { // bitmap[0] = 0000000000000 bitmap[1] = 0000000000000
                    j++; // 2
                    matches++; // 2
                }
                if (matches != reqrd_pages) {
                    if (j < BIT_SIZE)
                        matches = 0;
                    continue;
                }
                j = start; // 0
                matches = 0; // 0
                while (j < BIT_SIZE && !((bitmap[i] >> j) & 0x1) && matches < reqrd_pages) {
                    bitmap[i] |= 1 << j; // // bitmap[i] = 0010001110011
                    j++; // 2
                    matches++; // 2
                }
                return (i * BIT_SIZE) + start + 1;
            }
        }
    }
    return -1;
};


int main() {



    Solution sol;
    n = 3
    int result = sol.alloc(3);
    cout << result;


    cout<<"Hello World";
    return 0;
}