Faits : A. Par jugement du 6 février 2018, le Tribunal correctionnel de la République et canton de Genève a acquitté X._ des chefs de prévention de contrainte sexuelle (art. 189 ch. 1 CP), de viol (art. 190 ch. 1 CP), d'actes d'ordre sexuel commis sur une personne incapable de discernement (art. 191 CP) et de lésions corporelles simples (art. 123 ch. 1 CP). B. Statuant le 8 mai 2019, la Chambre pénale d'appel et de révision a admis partiellement les appels formés par A._, partie plaignante, et par le ministère public contre le jugement du 6 février 2018. Elle l'a réformé en ce sens que X._ était condamné pour actes d'ordre sexuel commis sur une personne incapable de discernement (art. 191 CP) à une peine pécuniaire de 200 jours-amende, à 30 fr. l'unité, avec sursis pendant 2 ans, qu'il devait payer à A._ une indemnité de 4000 fr., avec intérêts à 5% l'an dès le 1 er février 2016, à titre de réparation du tort moral, un tiers des frais de procédure étant en outre mis à sa charge. Le jugement du 6 février 2018 a été confirmé pour le surplus. En substance, la cour cantonale a retenu les faits suivants. B.a. X._, né en 1977, et A._, née en 1994, se sont rencontrés en octobre 2015 lors d'un séjour à la Clinique B._. Le premier était suivi par les Hôpitaux C._ en raison d'un ostéosarcome diagnostiqué en 2013, dont la tumeur située sur le haut du fémur lui occasionnait d'importantes douleurs. Il avait ainsi subi plusieurs interventions ainsi que deux cycles de chimiothérapie durant l'année 2015, se déplaçant depuis lors en chaise roulante ou au moyen de béquilles. La seconde souffrait pour sa part de troubles psychiques, notamment d'un trouble dépressif récurrent, présentant en outre un retard mental moyen. En 2013, une curatrice lui avait été désignée par l'autorité de protection de l'adulte, l'intéressée ayant été privée de l'exercice des droits civils dans les domaines des affaires administratives courantes, de la gestion du patrimoine et dans les rapports juridiques avec les tiers. Après un séjour de X._ en Algérie, Etat dont il est ressortissant, les deux précités se sont revus à la fin janvier 2016. A cette période, et jusqu'au début février 2016, ainsi que le 13 mars 2016, ils ont entretenu des rapports sexuels dans le studio qu'occupait X._ à D._. B.b. Le 18 mars 2016, A._, accompagnée de sa curatrice, a déposé plainte contre X._, lui reprochant de l'avoir violentée et forcée à entretenir des rapports sexuels brutaux en date du 13 mars 2016. B.c. En cours d'instruction, A._ a été soumise à une expertise psychiatrique établie par le Dr E._, médecin à l'Unité de psychiatrie légale du Centre universitaire romand de médecine légale (CURML). Dans son rapport du 14 juillet 2016, l'expert a relevé que l'ensemble du tableau clinique de l'expertisée (retard mental moyen, trouble envahissant du développement et trouble dépressif récurrent) était assimilable à un trouble mental de gravité élevée. Ainsi, pour une personne ayant des capacités normales d'observation, le retard mental de l'expertisée, qui n'avait pas de stigmates physiques, apparaissait rapidement dans le cadre d'une conversation verbale. Un trouble du comportement au niveau sexuel a été mis en évidence sous forme d'une incapacité à comprendre les dimensions symboliques et affectives de ses comportements. A._ ne faisait pas la différence entre les pénétrations anale et vaginale dans leur description, alors qu'elle avait une perception relativement organisée de son corps et était capable de distinguer les différents actes sexuels. L'expertisée n'avait pas la capacité de discernement pour acquiescer à un rapport sexuel, dans la mesure où elle ne pouvait pas se déterminer. Ni son accord, ni son refus n'étaient l'expression d'une volonté construite. Elle était capable d'opposer un refus ou au contraire de se mettre dans une position de passivité et de laisser-faire, en fonction des circonstances et de la capacité de son interlocuteur. En outre, A._ n'avait pas une tendance normale à fabuler, mais elle avait une capacité à ne pas dire la vérité sans être en mesure d'élaborer des mensonges complexes, ni forcément chercher à mentir. C. X._ forme un recours en matière pénale contre l'arrêt du 8 mai 2019. Il conclut, avec suite de frais et dépens, principalement à son acquittement. Subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause à la cour cantonale pour nouvelle décision au sens des considérants. Il sollicite en outre le bénéfice de l'assistance judiciaire. Invitée à se déterminer sur le recours, la cour cantonale a renoncé à présenter des observations, se référant aux considérants de l'arrêt attaqué. Le Ministère public a conclu au rejet du recours. Quant à A._, elle a également conclu au rejet du recours. Elle a par ailleurs sollicité le bénéfice de l'assistance judiciaire.