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

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dGhyZWFkPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YXRvbWljPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOVU1fVEhSRUFEUyA9IDU7CmF0b21pYzxib29sPiBjaG9vc2luZ1tOVU1fVEhSRUFEU107CmF0b21pYzxpbnQ+IG51bWJlcltOVU1fVEhSRUFEU107CgovLyBVdGlsaXR5OiBHZXQgbWF4IHRpY2tldCBudW1iZXIKaW50IGdldF9tYXhfdGlja2V0KCkgewogICAgaW50IG1heF92YWwgPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOVU1fVEhSRUFEUzsgKytpKSB7CiAgICAgICAgbWF4X3ZhbCA9IG1heChtYXhfdmFsLCBudW1iZXJbaV0ubG9hZCgpKTsKICAgIH0KICAgIHJldHVybiBtYXhfdmFsOwp9CgovLyBCYWtlcnkgTG9jawp2b2lkIGxvY2soaW50IGlkKSB7CiAgICBjaG9vc2luZ1tpZF0gPSB0cnVlOwogICAgY291dCA8PCAiVGhyZWFkICIgPDwgaWQgPDwgIiBpcyBjaG9vc2luZyBhIHRpY2tldC4uLlxuIjsKICAgIG51bWJlcltpZF0gPSBnZXRfbWF4X3RpY2tldCgpICsgMTsKICAgIGNob29zaW5nW2lkXSA9IGZhbHNlOwoKICAgIGNvdXQgPDwgIlRocmVhZCAiIDw8IGlkIDw8ICIgZ290IHRpY2tldCAjIiA8PCBudW1iZXJbaWRdIDw8ICIgYW5kIGlzIHdhaXRpbmcgdG8gZW50ZXIuLi5cbiI7CgogICAgZm9yIChpbnQgaiA9IDA7IGogPCBOVU1fVEhSRUFEUzsgKytqKSB7CiAgICAgICAgd2hpbGUgKGNob29zaW5nW2pdKSB7fSAgLy8gd2FpdCB3aGlsZSBvdGhlciB0aHJlYWQgaXMgY2hvb3NpbmcKICAgICAgICB3aGlsZSAobnVtYmVyW2pdICE9IDAgJiYKICAgICAgICAgICAgICAobnVtYmVyW2pdIDwgbnVtYmVyW2lkXSB8fAogICAgICAgICAgICAgIChudW1iZXJbal0gPT0gbnVtYmVyW2lkXSAmJiBqIDwgaWQpKSkgewogICAgICAgICAgICAvLyBXYWl0aW5nIGZvciBpdHMgdHVybgogICAgICAgIH0KICAgIH0KfQoKLy8gQmFrZXJ5IFVubG9jawp2b2lkIHVubG9jayhpbnQgaWQpIHsKICAgIG51bWJlcltpZF0gPSAwOwp9CgovLyBDcml0aWNhbCBTZWN0aW9uIHNpbXVsYXRpb24Kdm9pZCBjcml0aWNhbF9zZWN0aW9uKGludCBpZCkgewogICAgbG9jayhpZCk7CgogICAgY291dCA8PCAiVGhyZWFkICIgPDwgaWQgPDwgIiBpcyBFTlRFUklORyBjcml0aWNhbCBzZWN0aW9uLlxuIjsKICAgIHRoaXNfdGhyZWFkOjpzbGVlcF9mb3IoY2hyb25vOjptaWxsaXNlY29uZHMocmFuZCgpICUgMTUwMCArIDUwMCkpOwogICAgY291dCA8PCAiVGhyZWFkICIgPDwgaWQgPDwgIiBpcyBFWElUSU5HIGNyaXRpY2FsIHNlY3Rpb24uXG5cbiI7CgogICAgdW5sb2NrKGlkKTsKfQoKaW50IG1haW4oKSB7CiAgICAvLyBJbml0aWFsaXplCiAgICBmb3IgKGludCBpID0gMDsgaSA8IE5VTV9USFJFQURTOyArK2kpIHsKICAgICAgICBjaG9vc2luZ1tpXSA9IGZhbHNlOwogICAgICAgIG51bWJlcltpXSA9IDA7CiAgICB9CgogICAgLy8gTGF1bmNoIHRocmVhZHMKICAgIHZlY3Rvcjx0aHJlYWQ+IHRocmVhZHM7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE5VTV9USFJFQURTOyArK2kpIHsKICAgICAgICB0aHJlYWRzLmVtcGxhY2VfYmFjayhjcml0aWNhbF9zZWN0aW9uLCBpKTsKICAgICAgICB0aGlzX3RocmVhZDo6c2xlZXBfZm9yKGNocm9ubzo6bWlsbGlzZWNvbmRzKDMwMCkpOyAvLyBzaW11bGF0ZSByYW5kb20gYXJyaXZhbCBsaWtlIGN1c3RvbWVycwogICAgfQoKICAgIGZvciAoYXV0byAmdCA6IHRocmVhZHMpIHsKICAgICAgICB0LmpvaW4oKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=