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:;
  }
}