CODE FESTIVAL 2016 Final

Submission #1005690

Source codeソースコード

#include <cstdio>
#include <cmath>

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("%2d ", ll[i]);
	inc(j, n) {
		printf("%c ", out[i][j] ? '.' : cc[ dir[i][j] - 4 ]);
	} printf("%2d\n", rr[i]);
	} printf("");
	
	printf("   "); inc(j, n) { printf("%2d", dd[j]); } printf("\n\n");
	
}

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

bool search(int i, int j, bool i_flag) {
	inc(i, n) {
	inc(j, n) {
		vis[i][j] = false;
	}
	}
	return _search(i, j, i_flag);
}

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; } // |
	}
	inc(i, n) {
	inc(j, n) {
		if(dir[i][j] == 0) { ei[i]++; ej[j]++; }
	}
	}
	inc(i, n) {
	inc(j, n) {
		if(dir[i][j] == 3) {
			if(! search(i, j, true) && ! search(i, j, false)) { printf("NO\n"); return 0; }
		}
	}
	}
	
	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); }
		}
	}
	
	
	
	
	inc(i, n) {
		uu[i] = ll[i] = 0;
		dd[i] = rr[i] = n - 1;
	}
	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++;
			}
		}
		
		if(nn == pnn) {
			inc(i, n) {
			inc(j, n) {
				vis[i][j] = false;
			}
			}
			
			inc(j, n) {
				if(uu[j] < n) {
					int i = uu[j], v;
					int di[4] = { -1, 1,  0, 0 };
					int dj[4] = {  0, 0, -1, 1 };
					
					do {
						vis[i][j] = true;
						v = dir[i][j];
						do { i += di[v - 4]; j += dj[v - 4]; } while(out[i][j]);
					} while(! vis[i][j]);
					
					v = dir[i][j];
					int oi = i, oj = j;
					do {
						do { i += di[v - 4]; j += dj[v - 4]; } while(out[i][j]);
						swap(v, dir[i][j]);
					} while(i != oi || j != oj);
					
					break;
				}
			}
		}
		pnn = nn;
	}
	
	return 0;
}

Submission

Task問題 J - Neue Spiel
User nameユーザ名 FF256grhy
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 2100
Source lengthソースコード長 5786 Byte
File nameファイル名
Exec time実行時間 1250 ms
Memory usageメモリ使用量 1152 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘void print3()’:
./Main.cpp:63:13: warning: zero-length gnu_printf format string [-Wformat-zero-length]
} printf("");
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:128:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:129: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:130: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:131: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]); }
...

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 2000 / 2000 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt
dataset2 100 / 100 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 128 KB
01-02.txt AC 1 ms 128 KB
01-03.txt AC 1 ms 128 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 2 ms 256 KB
01-07.txt AC 2 ms 256 KB
01-08.txt AC 2 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 2 ms 256 KB
01-11.txt AC 2 ms 256 KB
01-12.txt AC 2 ms 256 KB
01-13.txt AC 2 ms 256 KB
01-14.txt AC 1 ms 128 KB
01-15.txt AC 2 ms 256 KB
01-16.txt AC 2 ms 256 KB
01-17.txt AC 2 ms 256 KB
01-18.txt AC 2 ms 256 KB
01-19.txt AC 1 ms 128 KB
01-20.txt AC 3 ms 256 KB
01-21.txt AC 2 ms 256 KB
01-22.txt AC 1 ms 128 KB
01-23.txt AC 1 ms 128 KB
01-24.txt AC 3 ms 256 KB
01-25.txt AC 3 ms 256 KB
01-26.txt AC 1 ms 128 KB
01-27.txt AC 2 ms 256 KB
01-28.txt AC 2 ms 256 KB
01-29.txt AC 3 ms 256 KB
01-30.txt AC 2 ms 256 KB
01-31.txt AC 1 ms 128 KB
01-32.txt AC 3 ms 256 KB
01-33.txt AC 1 ms 128 KB
01-34.txt AC 2 ms 256 KB
01-35.txt AC 2 ms 256 KB
01-36.txt AC 2 ms 256 KB
01-37.txt AC 1 ms 128 KB
01-38.txt AC 2 ms 256 KB
01-39.txt AC 2 ms 256 KB
01-40.txt AC 3 ms 256 KB
01-41.txt AC 3 ms 256 KB
01-42.txt AC 3 ms 256 KB
01-43.txt AC 2 ms 256 KB
01-44.txt AC 2 ms 256 KB
01-45.txt AC 2 ms 256 KB
01-46.txt AC 2 ms 256 KB
02-01.txt AC 1083 ms 1152 KB
02-02.txt AC 1058 ms 1152 KB
02-03.txt AC 331 ms 1152 KB
02-04.txt AC 1115 ms 1152 KB
02-05.txt AC 1 ms 128 KB
02-06.txt AC 1 ms 128 KB
02-07.txt AC 1122 ms 1152 KB
02-08.txt AC 1250 ms 1152 KB
02-09.txt AC 854 ms 1152 KB
02-10.txt AC 854 ms 1152 KB
02-11.txt AC 854 ms 1152 KB
02-12.txt AC 854 ms 1152 KB
sample-01.txt AC 1 ms 128 KB
sample-02.txt AC 1 ms 128 KB