Submission #1005542

---

Source Code Expand

#include <cstdio>
#include <cmath>

#include <queue>
#include <utility>

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define inc( i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec( i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

template<typename T> void swap(T & x, T & y) { T t = x; x = y; y = t; return; }
template<typename T> T abs(T x) { return (0 <= x ? x : -x); }
template<typename T> T max(T a, T b) { return (b <= a ? a : b); }
template<typename T> T min(T a, T b) { return (a <= b ? a : b); }
template<typename T> bool setmin(T & a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T & a, T b) { if(b <= a) { return false; } else { a = b; return true; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, u[300], d[300], l[300], r[300];
int dir[300][300];

int uu[300], dd[300], ll[300], rr[300], nn;
bool out[300][300];

void print() {
	char cc[] = { '.', '-', 'l', '+' };
	inc(i, n) {
	inc(j, n) {
		printf("%c ", cc[ dir[i][j] ]);
	} printf("\n");
	} printf("\n");
}

void print2() {
	char cc[] = { '^', 'v', '(', '>' };
	inc(i, n) {
	inc(j, n) {
		printf("%c ", cc[ dir[i][j] - 4 ]);
	} printf("\n");
	} printf("\n");
}

void print3() {
	char cc[] = { '^', 'v', '(', '>' };
	
	printf(" "); inc(j, n) { printf("%2d", uu[j]); } printf("\n");
	
	inc(i, n) { printf("%d ", ll[i]);
	inc(j, n) {
		printf("%c ", out[i][j] ? '.' : cc[ dir[i][j] - 4 ]);
	} printf(" %d\n", rr[i]);
	} printf("");
	
	printf(" "); inc(j, n) { printf("%2d", dd[j]); } printf("\n\n");
	
}

bool vis_i[300], vis_j[300];
bool search(int i, int j, bool i_flag) {
	if(dir[i][j] == 0) {
		dir[i][j] = (i_flag ? 1 : 2);
		return true;
	}
	
	if(i_flag) {
		inc(ii, n) {
			if(! vis_i[ii] && dir[ii][j] / 2 == 0) {
				vis_i[ii] = true;
				if(search(ii, j, ! i_flag)) { dir[i][j] = 1; return true; }
			}
		}
	} else {
		inc(jj, n) {
			if(! vis_j[jj] && dir[i][jj] % 2 == 0) {
				vis_j[jj] = true;
				if(search(i, jj, ! i_flag)) { dir[i][j] = 2; return true; }
			}
		}
	}
	
	return false;
}

int main() {
	scanf("%d", &n);
	inc(i, n) { scanf("%d", &u[i]); }
	inc(i, n) { scanf("%d", &d[i]); }
	inc(i, n) { scanf("%d", &l[i]); }
	inc(i, n) { scanf("%d", &r[i]); }
	
	inc(i, n) { if(u[i] + d[i] > n || l[i] + r[i] > n) { printf("NO\n"); return 0; } }
	
	
	inc(i, n) {
	inc(j, n) {
		dir[i][j] = 0;
	}
	}
	inc(i, n) {
		inc(j, l[i] + r[i]) { dir[i][j] += 1; } // -
	}
	inc(j, n) {
		inc(i, u[j] + d[j]) { dir[i][j] += 2; } // |
	}
	
	// print();
	
	inc(i, n) {
	inc(j, n) {
		if(dir[i][j] == 3) {
			inc(ii, n) { vis_i[ii] = false; }
			inc(jj, n) { vis_j[jj] = false; }
			vis_i[i] = true;
			vis_j[j] = true;
			if(! search(i, j, true) && ! search(i, j, false)) { printf("NO\n"); return 0; }
		}
	}
	}
	
	// print();
	
	inc(j, n) {
		int c = 0;
		inc(i, n) {
			if(dir[i][j] == 2) { dir[i][j] = (c++ < u[j] ? 4 : 5); }
		}
	}
	inc(i, n) {
		int c = 0;
		inc(j, n) {
			if(dir[i][j] == 1) { dir[i][j] = (c++ < l[i] ? 6 : 7); }
		}
	}
	
	// print2();
	
	
	inc(i, n) {
		uu[i] = ll[i] = 0;
		dd[i] = rr[i] = n - 1;
	}
	
	// print3();
	
	int pnn = 0;
	while(nn < n * n) {
		inc(j, n) {
			while(uu[j] < n && out[ uu[j] ][j]) { uu[j]++; }
			if(uu[j] < n && dir[ uu[j] ][j] == 4) {
				printf("U%d\n", j + 1);
				out[ uu[j] ][j] = true;
				nn++;
			}
		}
		inc(j, n) {
			while(dd[j] >= 0 && out[ dd[j] ][j]) { dd[j]--; }
			if(dd[j] >= 0 && dir[ dd[j] ][j] == 5) {
				printf("D%d\n", j + 1);
				out[ dd[j] ][j] = true;
				nn++;
			}
		}
		inc(i, n) {
			while(ll[i] < n && out[i][ ll[i] ]) { ll[i]++; }
			if(ll[i] < n && dir[i][ ll[i] ] == 6) {
				printf("L%d\n", i + 1);
				out[i][ ll[i] ] = true;
				nn++;
			}
		}
		inc(i, n) {
			while(rr[i] >= 0 && out[i][ rr[i] ]) { rr[i]--; }
			if(rr[i] >= 0 && dir[i][ rr[i] ] == 7) {
				printf("R%d\n", i + 1);
				out[i][ rr[i] ] = true;
				nn++;
			}
		}
		
		// print3();
		if(nn == pnn) {
			inc(j, n) {
				if(uu[j] < n) {
					int i = uu[j];
					int oi = i, oj = j;
					int v = dir[i][j];
					int di[4] = { -1, 1,  0, 0 };
					int dj[4] = {  0, 0, -1, 1 };
					do {
						do { i += di[v - 4]; j += dj[v - 4]; } while(out[i][j]);
						int temp = dir[i][j];
						dir[i][j] = v;
						v = temp;
					} while(i != oi && j != oj);
					
					break;
				}
			}
		}
		pnn = nn;
	}
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void print3()’:
./Main.cpp:66:13: warning: zero-length gnu_printf format string [-Wformat-zero-length]
  } printf("");
             ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:99:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:100:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  inc(i, n) { scanf("%d", &u[i]); }
                                ^
./Main.cpp:101:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  inc(i, n) { scanf("%d", &d[i]); }
                                ^
./Main.cpp:102:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  inc(i, n) { scanf("%d", &l[i]); }
                             ...

Judge Result