2208 トーマス・ライトの憂鬱
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2208&lang=jp
方針
決められるところから全部決めていってしまう。
全部決められなければ、解はない。
ソース
#include<cstdio> #include<algorithm> using namespace std; int rows[10001],cols[10001]; int main() { int n; while(scanf("%d", &n), n) { for(int i=0; i<n; ++i) scanf("%d", rows+i); for(int i=0; i<n; ++i) scanf("%d", cols+i); sort(rows, rows+n); sort(cols, cols+n); int csize = n,rsize = n; int front = 0,back = n-1; while(1) { int pf = front,pb = back; while(rows[back] == rsize) { csize--; for(int i=front; i<n; ++i) cols[i]--; back--; if(back == -1) break; } while(cols[front] == 0) { rsize--; front++; if(front == n || back == -1) goto END; } if(pf == front && pb == back) break; } END:; for(int i=0; i<n; ++i) { if(cols[i] > 0) { printf("No\n"); goto NEXT; } } printf("Yes\n"); NEXT:; } }