Two-tailed one-sample permutation test I want to test the significance of the classification accuracy of a cross-validated binary classifier.
I performed a permutation test to determine whether the true classification accuracy is higher than the chance level classification accuracy:

How to perform a two-tailed version of such a test?
 A: In many cases the P-value of a 2-sided test is twice the P-value of
a 1-sided test.
For demonstration purposes, here are descriptions of a sample of size $n = 100$ from a Laplace distribution
(centered at 2 and with much heavier tails than normal).
summary(x)
    Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
-13.0858  -0.2901   1.0873   0.8850   1.8196  11.6360 
sd(x);  length(x)
[1] 3.122601
[1] 100

boxplot(x, col="skyblue2", pch = 20, horizontal=T)


Here is a permutation test, in R,  of $H_0: \mu = 0$ vs $H_a: \mu \ne 0.$
At each iteration, the sign of each observation is randomly changed between $\pm 1.$ At each iteration, the mean of the sign-permuted data is found.
[That is, the 'metric' of the permutation test is the sample mean.]
The observed mean of the sample is 1.885. 
set.seed(1234)
a.obs = mean(x)
a.prm = replicate(10^5, mean(sample(c(-1,1),100,rep=T)*x) )
mean(abs(a.prm) >= abs(a.obs))
[1] 0.00496                     # P-value of two-sided test

hist(a.prm, prob=T, col="skyblue2", xlim=c(-7,7))
abline(v=c(a.obs,-a.obs), col="red")


The P-value of the two-sided test is the area in both tails beyond
the vertical red lines.
For a one-sided test (against $H_a: \mu > 0,$ the P-value would be
the value in the right tail beyond 0.885. R-code 'mean(a.prm >= a.obs)`,
which returns 0.00223.  
Notes: (1) In the R code for the P-values, the vector with >= is
a logical vector with $10^5$ TRUEs and FALSEs, and the mean is
the proportion of its TRUEs. (2) Eudey et al. has an elementary presentation of permutation tests; Sect. 2 on paired tests is similar to your one-sample test.
A: If you have collected $N$ permutation scores, $s_1,\ldots,s_N$, the two-sided p-value for a treshold, $t$, can be estimated as $p_2(t) = {\rm min}(2\frac{|\{ s_i \geq t\}|}{N}, 2(1-\frac{|\{s_i \geq t\}|}{N}))$. I.e. just divide 2 times the number of permutations with scores greater or equal to your treshold with the total number of permutations. If the resulting value is less than one, then use the value directly, othervise subtract the value from 2.
