Deadlock after notify_one() (notifying thread locks mutex)

I have following problem. I have some multiple threads that do some work and one main thread that wakes them up when work is available. So far, I have managed to write some code using conditional variables and mutexes and most of the time this works okay, but from time to time, notifying thread will lock the mutex right after call notify_one(), thus blocking the notified thread and deadlocking.

I have written minimal code to illustrate this situation.

#include <iostream>
#include <thread>
#include <condition_variable>

std::mutex lock;
std::condition_variable cv;

void foo() {
    std::cout << "Thread: Entering doWork()" << std::endl;
    std::unique_lock<std::mutex> l(lock);
    std::cout << "Thread: Acquired lock, going to wait." << std::endl;
    cv.wait(l , []{return true;});
    std::cout << "Thread: Done waiting, exit." << std::endl;
}

int main(void) {
    std::unique_lock<std::mutex> l(lock);
    std::cout << "MAIN: Creating thread." << std::endl;
    std::thread t(foo);
    std::cout << "MAIN: Unlocking mutex." << std::endl;
    l.unlock();
    std::cout << "MAIN: Notifying thread." << std::endl;
    cv.notify_one();
    //std::this_thread::sleep_for(std::chrono::seconds(1));
    l.lock();
    std::cout << "MAIN: Acquired lock." << std::endl;
    std::cout << "MAIN: Joining thread." << std::endl;
    t.join();
    return 0;
}

In ideal situation, the output should be

MAIN: Creating thread.
MAIN: Unlocking mutex.
Thread: Entering doWork()
Thread: Acquired lock, going to wait.
MAIN: Notifying thread.
Thread: Done waiting, exit.
MAIN: Acquired lock.
MAIN: Joining thread.

but more often than not it is

MAIN: Creating thread.
MAIN: Unlocking mutex.
MAIN: Notifying thread.
MAIN: Acquired lock.
MAIN: Joining thread.
Thread: Entering doWork()

Is there any better way to eliminate chance of deadlock except of adding sleep into notifying thread (which I don't want to do)? Thank you in advance.