I'm not $100$% sure about this one (please suggest any improvements), but here it goes:
Out of the three, at least two have the same parity by the Pigeonhole Principle. If all three have the same parity, choose $a$ and $b$. Call the two chosen numbers $x$ and $y$, where $x>y$. The mean is ${x+y}\over2$, which is an integer since they both have the same parity. Again, by the Pigeonhole Principle, at least one of $x$ and $y$ must be an extremum (that is to say, either a maximum or minimum). Replace that with ${x+y}\over2$. (If one is maximum and the other minimum, $y$). Since $x$ and $y$ have the same parity (and they are not equal, otherwise we are done), we have $x-y\ge 2$.
Suppose we chose $x$, then the original triplet was $x,y,z$ in decreasing order (since we chose $x$, it is an extremum, and $x>y$ so it's a max. Since we didn't choose $y$, it isn't a minimum) for some $z$. The new triplet is ${x+y\over2},y,z$.
$${x+y\over2}<{x+x\over2} = x$$ since $x>y$. The new triplet still consists of integers, and $x - {x+y\over2} \ge 1$, so the bounds (that is max$(a,b,c)-$min$(a,b,c)$ have decreased by at least $1$. A similar argument works if we choose $y$ (Original - $p,q,y$ - since we don't know whether or not $x$ is the largest, new $p,q,{x+y\over2}$, $y<{x+y\over2}$).
At every step, the bounds decrease by at least $1$ (either due to a decrease in maximum or an increase in minimum). Thus there must come a stage the values are 'squeezed', and either $a=b,b=c$ or $a=c$.
Here is a python code that implements the above algorithm (can someone make the syntax highlighting appear?):
a = int(input())
b = int(input())
c = int(input())
g = 0
m = 0
ma = 0
mb = 0
mc = 0
x = 0
if a == b or b == c or a == c:
print("Condition already satisfied")
else:
print(str(a)+", "+str(b)+", "+str(c))
while a!=b and b!=c and c!=a:
g = max(a,b,c)
m = min(a,b,c)
ma = a%2
mb = b%2
mc = c%2
if mb == ma:
x = (a+b)/2
if a == m or b == m:
if a == m:
a = x
if b == m:
b = x
else:
if a == g:
a = x
if b == g:
b = x
elif ma == mc:
x = (c+a)/2
if c == m or a == m:
if c == m:
c = x
if a == m:
a = x
else:
if c == g:
c = x
if a == g:
a = x
elif mb == mc:
x = (c+b)/2
if c == m or b == m:
if c == m:
c = x
if b == m:
b = x
else:
if c == g:
c = x
if b == g:
b = x
print(str(a)+", "+str(b)+", "+str(c))
Maybe someone can implement this logic in C++ since I don't know that.