Sachverhalt: A. X._ und A._ lernten sich am frühen Morgen des 5. Dezember 2010 nach dem Ausgang kennen. Die beiden fuhren per Taxi an die B._-strasse in Zürich-Wollishofen, wo X._ vorübergehend wohnte. Im Trocknungsraum kam es zu Vaginal- und Analverkehr. Dieser war nach Darstellung von A._ unfreiwillig, nach jener von X._ einvernehmlich. B. Das Bezirksgericht Zürich verurteilte X._ am 24. Mai 2011 wegen Vergewaltigung und sexueller Nötigung zu einer Freiheitsstrafe von dreieinviertel Jahren. X._ erhob Berufung. Das Obergericht des Kantons Zürich sprach ihn am 13. Dezember 2011 zweitinstanzlich vollumfänglich frei. Es verpflichtete die Staatskasse, ihm Fr. 5'000.-- als Schadenersatz und Fr. 60'000.-- als Genugtuung zu bezahlen, je zuzüglich Zins zu 5 % ab dem Urteilsdatum. C. C.a Gegen dieses Urteil erhebt die Oberstaatsanwaltschaft des Kantons Zürich Beschwerde in Strafsachen (Verfahren 6B_122/2012). Sie beantragt, das angefochtene Urteil sei aufzuheben. Die Sache sei zur neuen Beurteilung an die Vorinstanz zurückzuweisen. X._ beantragt mit Eingabe vom 12. April 2012, die Beschwerde der Oberstaatsanwaltschaft sei unter Kosten- und Entschädigungsfolgen abzuweisen. Eventualiter sei ihm die unentgeltliche Rechtsvertretung zu bewilligen. Das Obergericht des Kantons Zürich verzichtete auf eine Stellungnahme. C.b X._ erhebt gegen das Urteil des Obergerichts des Kantons Zürich vom 13. Dezember 2011 ebenfalls Beschwerde in Strafsachen (Verfahren 6B_111/2012). Er beantragt, das Urteil sei hinsichtlich seiner Schadenersatz- und Genugtuungsansprüche aufzuheben. Es seien ihm Fr. 39'354.35 als Schadenersatz und Fr. 100'000.-- als Genugtuung nebst Zins seit dem 13. Dezember 2011 zuzusprechen, unter Kosten- und Entschädigungsfolgen zu Lasten der Staatskasse. Eventualiter sei ihm die unentgeltliche Prozessführung und Verbeiständung zu bewilligen. Das Obergericht des Kantons Zürich und die Oberstaatsanwaltschaft verzichteten auf eine Stellungnahme. 