Such a constant $c$, not depending on $k$ and $x_1,\dots,x_k$, does not exist.

Indeed, suppose $k\ge2$. Let $x_i:=(i-1)h$ for $i=0,\dots,k+1$, where $h:=\frac1{k-1}$ -- so that $x_1=0$ and $x_k=1$.

Take any $(y_1,\dots,y_k)\in A(x_1,\dots,x_k)$. Then there exist intervals $I_1,\dots,I_k$ in $[0,1]$
such that $x_i,y_i\in I_i$ and $|\cup_iI_i|\leq\frac12$; here $|\cdot|$ denotes the Lebesgue measure in any dimensions. Without loss of generality (w.l.o.g.), we can replace here each $I_j$ by $[x_j\wedge y_j,x_j\vee y_j]$, so that w.l.o.g. each $I_j$ is closed. So, for some $m=1,\dots,k$, there exist disjoint nonempty closed subintervals $J_1,\dots,J_m$ of $[0,1]$ such that $I_1\cup\dots\cup I_k=J_1\cup\dots\cup J_m\supseteq\{x_1,\dots,x_k\}$. So, w.l.o.g. there are natural $n_1,\dots,n_m$ and real $a_1,b_1,\dots,a_m,b_m$ such that $a_1=0$, $b_m=1$, $n_1<\dots<n_m=k$, $J_i=[a_i,b_i]$ for all $i=1,\dots,m$, and $x_{n_i}\le b_i<a_{i+1}\le x_{n_i+1}$ for all $i=1,\dots,m-1$.
So, $\{x_{n_{i-1}+1},\dots,x_{n_i}\}\subseteq J_i$ and hence $\{y_{n_{i-1}+1},\dots,y_{n_i}\}\subseteq J_i=[a_i,b_i]\subseteq[x_{n_{i-1}},x_{n_i+1}]$ for all $i=1,\dots,m$, with $n_0:=0$.
For $i=1,\dots,m$, let $\ell_i:=n_i-n_{i-1}$, so that $\sum_1^m\ell_i=k$ and the length of the interval $[x_{n_{i-1}},x_{n_i+1}]$ is $(\ell_i+1)h\le2\ell_i h$.
So, the Lebesgue measure of the set of all $(y_1,\dots,y_k)\in A(x_1,\dots,x_k)$ with given $n_1,\dots,n_m$ is no greater than $\prod_1^m(2\ell_i h)^{\ell_i}=(2h)^k\prod_1^m\ell_i^{\ell_i}$.
On the other hand, the cardinality (say $N$) of the set of all $m$-tuples $(n_1,\dots,n_m)$ of natural numbers such that $m\in\{1,\dots,k\}$ and $n_1<\dots<n_m=k$ is no greater than $2^k$ (consider the indicators of the sets $\{n_1,\dots,n_m\}$).

The crucial observation is that $a_{i+1}-b_i\le x_{n_i+1}-x_{n_i}=h$ for all $i=1,\dots,m-1$ and hence
$\frac12\le|[0,1]\setminus(J_1\cup\dots\cup J_m)|=\sum_1^{m-1}(a_{i+1}-b_i)\le(m-1)h$, so that
\begin{equation}
m-1\ge\frac1{2h}=\frac{k-1}2.
\end{equation}
Therefore and because $\sum_1^m\ell_i=k$, for $L:=\max_i\ell_i$ we have $k\ge L+(m-1)\ge L+\frac{k-1}2$, whence $L\le\frac{k+1}2\le\frac{3k}4$.

Thus,
\begin{equation}
|A(x_1,\dots,x_k)|\le N(2h)^k\max\Big\{\prod_1^k\ell_i^{\ell_i}\colon
\sum_1^k\ell_i=k,0\le\ell_i\le\tfrac{3k}4\ \forall i\Big\},
\end{equation}
with $0^0:=1$.
Since $\ln(u^u)=u\ln u$ is convex in $u>0$, it follows that $\prod_1^k\ell_i^{\ell_i}$ is Schur-convex in the $\ell_i$'s, so that for any fixed real $c>0$
\begin{equation}
|A(x_1,\dots,x_k)|\le N(2h)^k(\tfrac{3k}4)^{3k/4}
\le \frac{4^k}{(k-1)^k}\,k^{3k/4}=o(c^k)
\end{equation}
as $k\to\infty$.