JOI2008予選 問題3@C++(12)
今までこれは太郎と花子の配列を別で管理しないといけないと思ってたけど、さっきPerl版書いてる時に、他に方法ないかなと考えたら、一つの配列で一括して管理できることに気がついた。それと番兵法。
playerの入れ替えで減算ではなくxorを使っているのに特に理由はない。
#include <cstdio> #include <algorithm> #include <vector> using namespace std; int main(int argc, char* argv[]) { int n; scanf("%d\n",&n); vector<int> cards(n*2+1,1); for(int i=0;i<n;i++) { int current; scanf("%d\n",¤t); cards[--current]=0; } cards[n*2]=-1; vector<int> points(2,n); int player=0; int start=0; while(points[0] && points[1]) { for(int i=start;;i++) { if(cards[i]==player) { cards[i]=-2; points[player]--; start=i; break; } else if(cards[i]==-1) { start=0; break; } } player^=1; } printf("%d\n",points[1]); printf("%d\n",points[0]); return 0; }