OpenMP critical section only if data race exists vs lock?

My question is somewhat similar to this one: How to use lock in OpenMP? in the sense that their answers sort of answer my question but not well enough.

I'm trying to implement a simple work-stealing scheduler in OpenMP (from scratch).

Let's say I have an array of some object, say int. I have multiple threads which will manipulate the entries of this array, in no particular order. I would like to make sure that no two threads try to access the same element of the array at the same time. However, I am allowing the threads to access the same element, as long as the accesses are not simultaneous. Also, I am allowing the threads to access the array simultaneously, as long as each thread wishes to access a different entry of the array during this time. I could use a critical section, as in the following:

int array[1000];

#pragma omp parallel
{
    bool flag = true;
    while(flag){
        int x = rand()%1000;
        #pragma omp critical
        {
            array[x] = some_function(array[x]);
            if (some_condition(array[x])){
                flag = false;
            }
        }

    }

}

This code creates some threads and the threads randomly access and manipulate entries of the array until some stopping condition that kills the thread. This code works fine, since the critical section ensures that no two threads will ever write to the array at the same time (in case they generated the same value of x). However, if at some time two threads do not happen to generate the same value of x, the critical section is redundant, as they threads are not accessing the same entry. Is there a way to make it so that a thread will stall if and only if the value of x it generated is the same as a thread that is currently also using x? Right now, this code is inefficient, and basically serial, even if every thread happens to generate a different value of x. I want to make it so they stall only if there is a collision.

Perhaps what I am looking for are locks ,but I am not sure. Are critical sections not the right way to go here?

Create an array of locks for every element. That way threads with different x values can run concurrently.

Something like this:

#include <stdlib.h>
#include <omp.h>

int main() 
{
    int array[1000];
    omp_lock_t locks[1000];

    for (int i = 0; i < 1000; i++)
        omp_init_lock(&locks[i]);

    #pragma omp parallel
    {
        bool flag = true;
        while(flag){
            int x = rand()%1000;
            omp_set_lock(&locks[x]);
            array[x] = some_function(array[x]);
            if (some_condition(array[x])){
                flag = false;
            }
            omp_unset_lock(&locks[x]);
        }
    }

    for (int i = 0; i < 1000; i++)
        omp_destroy_lock(&locks[i]);
}