#include <iostream>
#include <thread>
#include <vector>
#include <atomic>
#include <chrono>
#include <algorithm>
 
using namespace std;
 
const int NUM_CUSTOMERS = 5;
atomic<bool> choosing[NUM_CUSTOMERS];
atomic<int> number[NUM_CUSTOMERS];
 
// Utility: Get max ticket number
int get_max_ticket() {
    int max_val = 0;
    for (int i = 0; i < NUM_CUSTOMERS; ++i) {
        max_val = max(max_val, number[i].load());
    }
    return max_val;
}
 
// Bakery Lock
void lock(int id) {
    choosing[id] = true;
    cout << "Customer " << id << " is choosing a ticket...\n";
    number[id] = get_max_ticket() + 1;
    choosing[id] = false;
 
    cout << "Customer " << id << " got ticket #" << number[id] << " and is waiting to enter...\n";
 
    for (int j = 0; j < NUM_CUSTOMERS; ++j) {
        while (choosing[j]) {}  // wait while another customer is choosing
        while (number[j] != 0 &&
              (number[j] < number[id] ||
              (number[j] == number[id] && j < id))) {
            // busy wait
        }
    }
}
 
// Bakery Unlock
void unlock(int id) {
    number[id] = 0;
}
 
// Critical Section Simulation
void critical_section(int id) {
    lock(id);
 
    cout << "Customer " << id << " is ENTERING critical section.\n";
    this_thread::sleep_for(chrono::milliseconds(rand() % 1500 + 500));
    cout << "Customer " << id << " is EXITING critical section.\n\n";
 
    unlock(id);
}
 
int main() {
    // Initialize arrays
    for (int i = 0; i < NUM_CUSTOMERS; ++i) {
        choosing[i] = false;
        number[i] = 0;
    }
 
    // Launch customer threads
    vector<thread> customers;
    for (int i = 0; i < NUM_CUSTOMERS; ++i) {
        customers.emplace_back(critical_section, i);
        this_thread::sleep_for(chrono::milliseconds(300)); // staggered arrival
    }
 
    for (auto& c : customers) {
        c.join();
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dGhyZWFkPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YXRvbWljPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOVU1fQ1VTVE9NRVJTID0gNTsKYXRvbWljPGJvb2w+IGNob29zaW5nW05VTV9DVVNUT01FUlNdOwphdG9taWM8aW50PiBudW1iZXJbTlVNX0NVU1RPTUVSU107CgovLyBVdGlsaXR5OiBHZXQgbWF4IHRpY2tldCBudW1iZXIKaW50IGdldF9tYXhfdGlja2V0KCkgewogICAgaW50IG1heF92YWwgPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOVU1fQ1VTVE9NRVJTOyArK2kpIHsKICAgICAgICBtYXhfdmFsID0gbWF4KG1heF92YWwsIG51bWJlcltpXS5sb2FkKCkpOwogICAgfQogICAgcmV0dXJuIG1heF92YWw7Cn0KCi8vIEJha2VyeSBMb2NrCnZvaWQgbG9jayhpbnQgaWQpIHsKICAgIGNob29zaW5nW2lkXSA9IHRydWU7CiAgICBjb3V0IDw8ICJDdXN0b21lciAiIDw8IGlkIDw8ICIgaXMgY2hvb3NpbmcgYSB0aWNrZXQuLi5cbiI7CiAgICBudW1iZXJbaWRdID0gZ2V0X21heF90aWNrZXQoKSArIDE7CiAgICBjaG9vc2luZ1tpZF0gPSBmYWxzZTsKCiAgICBjb3V0IDw8ICJDdXN0b21lciAiIDw8IGlkIDw8ICIgZ290IHRpY2tldCAjIiA8PCBudW1iZXJbaWRdIDw8ICIgYW5kIGlzIHdhaXRpbmcgdG8gZW50ZXIuLi5cbiI7CgogICAgZm9yIChpbnQgaiA9IDA7IGogPCBOVU1fQ1VTVE9NRVJTOyArK2opIHsKICAgICAgICB3aGlsZSAoY2hvb3Npbmdbal0pIHt9ICAvLyB3YWl0IHdoaWxlIGFub3RoZXIgY3VzdG9tZXIgaXMgY2hvb3NpbmcKICAgICAgICB3aGlsZSAobnVtYmVyW2pdICE9IDAgJiYKICAgICAgICAgICAgICAobnVtYmVyW2pdIDwgbnVtYmVyW2lkXSB8fAogICAgICAgICAgICAgIChudW1iZXJbal0gPT0gbnVtYmVyW2lkXSAmJiBqIDwgaWQpKSkgewogICAgICAgICAgICAvLyBidXN5IHdhaXQKICAgICAgICB9CiAgICB9Cn0KCi8vIEJha2VyeSBVbmxvY2sKdm9pZCB1bmxvY2soaW50IGlkKSB7CiAgICBudW1iZXJbaWRdID0gMDsKfQoKLy8gQ3JpdGljYWwgU2VjdGlvbiBTaW11bGF0aW9uCnZvaWQgY3JpdGljYWxfc2VjdGlvbihpbnQgaWQpIHsKICAgIGxvY2soaWQpOwoKICAgIGNvdXQgPDwgIkN1c3RvbWVyICIgPDwgaWQgPDwgIiBpcyBFTlRFUklORyBjcml0aWNhbCBzZWN0aW9uLlxuIjsKICAgIHRoaXNfdGhyZWFkOjpzbGVlcF9mb3IoY2hyb25vOjptaWxsaXNlY29uZHMocmFuZCgpICUgMTUwMCArIDUwMCkpOwogICAgY291dCA8PCAiQ3VzdG9tZXIgIiA8PCBpZCA8PCAiIGlzIEVYSVRJTkcgY3JpdGljYWwgc2VjdGlvbi5cblxuIjsKCiAgICB1bmxvY2soaWQpOwp9CgppbnQgbWFpbigpIHsKICAgIC8vIEluaXRpYWxpemUgYXJyYXlzCiAgICBmb3IgKGludCBpID0gMDsgaSA8IE5VTV9DVVNUT01FUlM7ICsraSkgewogICAgICAgIGNob29zaW5nW2ldID0gZmFsc2U7CiAgICAgICAgbnVtYmVyW2ldID0gMDsKICAgIH0KCiAgICAvLyBMYXVuY2ggY3VzdG9tZXIgdGhyZWFkcwogICAgdmVjdG9yPHRocmVhZD4gY3VzdG9tZXJzOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOVU1fQ1VTVE9NRVJTOyArK2kpIHsKICAgICAgICBjdXN0b21lcnMuZW1wbGFjZV9iYWNrKGNyaXRpY2FsX3NlY3Rpb24sIGkpOwogICAgICAgIHRoaXNfdGhyZWFkOjpzbGVlcF9mb3IoY2hyb25vOjptaWxsaXNlY29uZHMoMzAwKSk7IC8vIHN0YWdnZXJlZCBhcnJpdmFsCiAgICB9CgogICAgZm9yIChhdXRvJiBjIDogY3VzdG9tZXJzKSB7CiAgICAgICAgYy5qb2luKCk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K