Training for Nightfall - 2017.07.21

ICPC Ranking

Nisiyama

#include <bits/stdc++.h>

int N, M, T, TF;

struct st {
	std::string name;
	int p[30];
	int suba[30];
	int subb[30];
	int subf[30];
	int last[30];
	st () {
		name = "";
		for (int i = 0; i < 30; ++i)
			p[i] = suba[i] = subb[i] = subf[i] = last[i] = 0;
	}
} team[51000];

struct re {
	std::string name;
	char p;
	int t;
	std::string res;
} rec[51000];

bool operator < (const re &a, const re &b) {
	if (a.t != b.t) return a.t < b.t;
	if (a.res == "ERROR" && (b.res == "NO" || b.res == "YES")) return true;
	if (a.res == "NO" && b.res == "YES") return true;
	return false;
}

struct cmp {
	bool operator () (int a, int b) {
		int cnta = 0, cntb = 0, pena = 0, penb = 0;
		for (int i = 0; i < M; ++i) {
			if (team[a].p[i] && team[a].subf[i] == 0) {
				++cnta;
				pena += team[a].suba[i] * 20;
				pena += team[a].last[i];
			}
			if (team[b].p[i] && team[b].subf[i] == 0) {
				++cntb;
				penb += team[b].suba[i] * 20;
				penb += team[b].last[i];
			}
		}
		if (cnta != cntb) return cnta > cntb;
		if (pena != penb) return pena < penb;
		static int lastla[30], lastlb[30];
		for (int i = 0; i < M; ++i) {
			if (team[a].p[i] && team[a].subf[i] == 0)
				lastla[i] = team[a].last[i];
			else
				lastla[i] = 0;
			if (team[b].p[i] && team[b].subf[i] == 0)
				lastlb[i] = team[b].last[i];
			else
				lastlb[i] = 0;
		}
		std::sort (lastla, lastla + M, std::greater <int> ());
		std::sort (lastlb, lastlb + M, std::greater <int> ());
		for (int i = 0; i < M; ++i)
			if (lastla[i] != lastlb[i])
				return lastla[i] < lastlb[i];
		return team[a].name > team[b].name;
	}
};

int team_size;
std::map <std::string, int> name;
std::set <int, cmp> board;

void put_board () {
	int rank = 0;
	for (auto it = board.begin (); it != board.end (); ++it) {
		int cnt = 0, pen = 0;
		for (int i = 0; i < M; ++i) 
			if (team[*it].p[i] && team[*it].subf[i] == 0) {
				++cnt;
				pen += team[*it].suba[i] * 20;
				pen += team[*it].last[i];
			}
		std::cout << team[*it].name << " " << ++rank << " " << cnt << " " << pen;
		for (int i = 0; i < M; ++i) {
			if (team[*it].subf[i] > 0)
				std::cout << " " << -team[*it].subb[i] << "/" << team[*it].subf[i];
			else {
				if (team[*it].p[i] > 0)
					if (team[*it].suba[i] > 0)
						std::cout << " +" << team[*it].suba[i];
					else
						std::cout << " +";
				else
					if (team[*it].suba[i] > 0)
						std::cout << " -" << team[*it].suba[i];
					else
						std::cout << " .";
			}
		}
		std::cout << std::endl;
	}
}

int main () {
	std::ios::sync_with_stdio (0);
	std::cin.tie (0);
	std::cout.tie (0);
	int C;
	std::cin >> C;
	for (int test = 0; test < C; ++test) {
		team_size = 0;
		name.clear ();
		board.clear ();
		std::cin >> N >> M >> T >> TF;
		for (int i = 0; i < N; ++i) 
			std::cin >> rec[i].name >> rec[i].p >> rec[i].t >> rec[i].res;
		std::sort (rec, rec + N);
		for (int i = 0; i < N; ++i) {
			int ind;
			if (name.find (rec[i].name) == name.end ()) {
				name[rec[i].name] = team_size++;
				team[team_size - 1] = st ();
				team[team_size - 1].name = rec[i].name;
				ind = team_size - 1;
			} else
				ind = name[rec[i].name];
			int p = rec[i].p - 'A';
			if (rec[i].t >= TF && (team[ind].subf[p] > 0 || team[ind].p[p] == 0))
				++team[ind].subf[p];
			if (rec[i].res == "YES") {
				if (team[ind].p[p] == 0) {
					team[ind].p[p] = 1;
					team[ind].last[p] = rec[i].t;
				}
			} else if (rec[i].res == "NO") {
				if (rec[i].t < TF)
					++team[ind].subb[p];
				if (team[ind].p[p] == 0)
					++team[ind].suba[p];
			}
		}
		for (int i = 0; i < team_size; ++i)
			board.insert (i);
		std::cout << "Case #" << test + 1 << ":" << std::endl;
		put_board ();
		auto it = --board.end ();
		for (; it != board.begin (); ) {
			int d = *(it--);
			board.erase (d);
			auto ot = board.lower_bound (d);
			for (int i = 0; i < M; ++i)
				if (team[d].subf[i] > 0) {
					team[d].subf[i] = 0;
					auto nt = board.lower_bound (d);
					if (nt == board.end ()) continue;
					if (nt != ot) {
						int cnt = 0, pen = 0;
						for (int i = 0; i < M; ++i) 
							if (team[d].p[i] && team[d].subf[i] == 0) {
								++cnt;
								pen += team[d].suba[i] * 20;
								pen += team[d].last[i];
							}
						std::cout << team[d].name << " " << team[*nt].name << " " << cnt << " " << pen << std::endl;
						break;
					}
				}
			board.insert (d);
		}
		for (int i = 0; i < M; ++i)
			team[*it].subf[i] = 0;
		put_board ();
	}
}

Simplified Chess Engine II

Aki

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> moves[4] = {{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}, {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}, {{-1, -1}, {1, 1}, {-1, 1}, {1, -1}}, {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};
struct board {
	char b[2][4][4];
	board() {memset(b, 0, sizeof(b));}
};
int id(char c) {
	int token;
	if (c == 'Q') token = 0;
	else if (c == 'N') token = 1;
	else if (c == 'B') token = 2;
	else if (c == 'R') token = 3;
	else if (c == 'P') token = 4;
	else token = -1;
	return token;
}
bool dfs(board bb, int step, int hand) {
	bool found_queen = 0;
	if (hand) step --;
	for (int x = 0; x < 4; ++ x) {
		for (int y = 0; y < 4; ++ y) {
			int type = id(bb.b[hand][x][y]);
			if (type == 0) found_queen = 1;
		}
	}
	if (!found_queen) return 0;
	if (step <= 0) return hand;
	bool win = 0;
	auto &w = bb.b[hand], &b = bb.b[hand ^ 1];
	for (int x = 0; x < 4 && !win; ++ x) {
		for (int y = 0; y < 4 && !win; ++ y) {
			int type = id(w[x][y]);
			if (type == -1) continue;
			if (type == 4) {
				int xx = x + (hand ? -1 : 1);
				int yy = y;
				if (!(xx >= 4 || yy >= 4 || xx < 0 || yy < 0 || b[xx][yy] || w[xx][yy])) {
					if (xx == (hand ? 0 : 3)) {
						swap(w[xx][yy], w[x][y]);
						for (char c : "NBR") {
							w[xx][yy] = c;
							if (!dfs(bb, step - (hand == 0), hand ^ 1)) win = 1;
							if (win) break;
						}
						w[xx][yy] = 'P';
						swap(w[xx][yy], w[x][y]);
					}
					else {
						swap(w[xx][yy], w[x][y]);
						if (!dfs(bb, step - (hand == 0), hand ^ 1)) win = 1;
						swap(w[xx][yy], w[x][y]);
					}
					if (win) break;
				}
				for (int d = -1; d <= 1; d += 2) {
					xx = x + (hand ? -1 : 1);
					yy = y + d;
					if (!(xx >= 4 || yy >= 4 || xx < 0 || yy < 0 || w[xx][yy]) && b[xx][yy]) {
						if (xx == (hand ? 0 : 3)) {
							swap(w[xx][yy], w[x][y]);
							char tmp = b[xx][yy];
							b[xx][yy] = 0;
							for (char c : "NBR") {
								w[xx][yy] = c;
								if (!dfs(bb, step - (hand == 0), hand ^ 1)) win = 1;
								if (win) break;
							}
							b[xx][yy] = tmp;
							w[xx][yy] = 'P';
							swap(w[xx][yy], w[x][y]);
						}
						else {
							swap(w[xx][yy], w[x][y]);
							char tmp = b[xx][yy];
							b[xx][yy] = 0;
							if (!dfs(bb, step - (hand == 0), hand ^ 1)) win = 1;
							b[xx][yy] = tmp;
							swap(w[xx][yy], w[x][y]);
						}
						if (win) break;
					}
				}
			}
			else for (int d = 0; d < (int) moves[type].size() && !win; ++ d) {
				for (int go = 1; !win; ++ go) {
					int xx = x + moves[type][d].first * go;
					int yy = y + moves[type][d].second * go;
					if (xx >= 4 || yy >= 4 || xx < 0 || yy < 0 || w[xx][yy]) break;
					swap(w[xx][yy], w[x][y]);
					char tmp = b[xx][yy];
					b[xx][yy] = 0;
					if (!dfs(bb, step - (hand == 0), hand ^ 1)) win = 1;
					b[xx][yy] = tmp;
					swap(w[xx][yy], w[x][y]);
					if (tmp) break;
				}
			}
		}
	}
	if (win) return 1;
	return 0;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		int w, b, m;
		scanf("%d%d%d", &w, &b, &m);
		board a = board();
		for (int i = 0; i < w; ++ i) {
			char op[3], c[3];
			int rr;
			scanf("%s%s%d", op, c, &rr);
			rr --;
			int cc = c[0] - 'A';
			a.b[0][rr][cc] = op[0];
		}
		for (int i = 0; i < b; ++ i) {
			char op[3], c[3];
			int rr;
			scanf("%s%s%d", op, c, &rr);
			rr --;
			int cc = c[0] - 'A';
			a.b[1][rr][cc] = op[0];
		}
		puts(dfs(a, m, 0) ? "YES" : "NO");
	}
}

Nisiyama

#include <bits/stdc++.h>

int mxq[16] = {1, 0, -1, 0, 1, 1, -1, -1, 2, 2, 1, 1, -2, -2, -1, -1};
int myq[16] = {0, 1, 0, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 2, -2};
int mb[4] = {0, 0, 4, 8};
int me[4] = {8, 4, 8, 16};
int mxp[2][3] = {{1, 1, 1}, {-1, -1, -1}};
int myp[2][3] = {{-1, 0, 1}, {-1, 0, 1}};
int nc[3] = {1, 0, 1};
char pro[3] = {'R', 'B', 'N'};

int tr (char c) {
	if (c == 'Q' || c == 'q') return 0;
	if (c == 'R' || c == 'r') return 1;
	if (c == 'B' || c == 'b') return 2;
	if (c == 'N' || c == 'n') return 3;
	if (c == 'P' || c == 'p') return 4;
	return -1;
}

int trh (char c) {
	const char s[] = ".QRBNPqrbnp\0";
	for (int i = 0; s[i]; ++i) {
		if (s[i] == c) return i;
	}
	return -1;
}

bool is_same (char a, char b) {
	return !((a >= 'A' && a <= 'Z') ^ (b >= 'A' && b <= 'Z'));
}

bool is_valid (int x, int y) {
	return x >= 0 && y >= 0 && x < 4 && y < 4;
}

char map[4][4];
std::map <long long, bool> mem;

long long hash (int mv, int rem) {
	long long ans = 0;
	for (int i = 0; i < 4; ++i)
		for (int j = 0; j < 4; ++j)
			ans = ans * 11 + trh (map[i][j]);
	ans = ans * 2 + mv;
	ans = ans * 10 + rem;
	return ans;
}

bool search (int mv, int rem) {
	if (rem == 0) return mv;
	if (mem.find (hash (mv, rem)) != mem.end ()) return mem[hash (mv, rem)];
	for (int real = 0; real < 2; ++real)
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j) {
				if (map[i][j] != '.' && ((map[i][j] >= 'A' && map[i][j] <= 'Z') ^ mv)) {
					char oc = map[i][j];
					int tp = tr (oc);
					if (tp <= 3) {
						for (int k = mb[tp]; k < me[tp]; ++k) {
							int nx = i + mxq[k], ny = j + myq[k];
							while (is_valid (nx, ny) && (map[nx][ny] == '.' || (!is_same (map[nx][ny], oc)))) {
								char on = map[nx][ny];
								if (on == 'q' || on == 'Q') return mem[hash (mv, rem)] = true;
								if (real) {
									map[nx][ny] = oc; map[i][j] = '.';
									bool re = search (mv ^ 1, rem - 1);
									map[nx][ny] = on; map[i][j] = oc;
									if (!re) return mem[hash (mv, rem)] = true;
								}
								if (map[nx][ny] != '.' || tp == 3) break;
								nx += mxq[k]; ny += myq[k];
							}
						}
					} else if (tp == 4) {
						for (int k = 0; k < 3; ++k) {
							int nx = i + mxp[mv][k], ny = j + myp[mv][k];
							if (!is_valid (nx, ny)) continue;
							if (!(nc[k] ^ (map[nx][ny] == '.'))) continue;
							if (map[nx][ny] != '.' && is_same (oc, map[nx][ny])) continue;
							char on = map[nx][ny];
							if (on == 'q' || on == 'Q') return mem[hash (mv, rem)] = true;
							if (real) {
								if ((mv == 0 && nx == 3) || (mv == 1 && nx == 0)) {
									for (int l = 0; l < 3; ++l) {
										map[nx][ny] = oc - 'P' + pro[l]; map[i][j] = '.';
										bool re = search (mv ^ 1, rem - 1);
										map[nx][ny] = on; map[i][j] = oc;
										if (!re) return mem[hash (mv, rem)] = true;
									}
								} else {
									map[nx][ny] = oc; map[i][j] = '.';
									bool re = search (mv ^ 1, rem - 1);
									map[nx][ny] = on; map[i][j] = oc;
									if (!re) return mem[hash (mv, rem)] = true;
								}
							}	
						}
					}
				}
			}
	return mem[hash (mv, rem)] = false;
}

int main () {
	int G;
	scanf ("%d", &G);
	for (int game = 0; game < G; ++game) {
		mem.clear ();
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j)
				map[i][j] = '.';
		int W, B, M;
		scanf ("%d%d%d", &W, &B, &M);
		for (int i = 0; i < W; ++i) {
			char a, b, c;
			scanf (" %c %c %c", &a, &b, &c);
			map[c - '1'][b - 'A'] = a;
		}
		for (int i = 0; i < B; ++i) {
			char a, b, c;
			scanf (" %c %c %c", &a, &b, &c);
			map[c - '1'][b - 'A'] = a - 'A' + 'a';
		}
		if (search (0, M))
			puts ("YES");
		else
			puts ("NO");
	}
	return 0;
}

lbn187

4*4棋盘 2个人 每人一个王后,最多两个兵,两个车,两个马/象 白兵向上走,黑兵向下走,一步只能走一格 兵走到底可以变成车/象/马 目标:吃掉地方王后

白先走,判断白棋在m步以内是否会赢

不超过1000局 第一行 w 白棋数 b 黑棋数 m步数限制 接下来几行 第一个字母描述棋子(Q后 P兵 N马 R车 B象) 第二个字母表示列(从左到右A–>D) 第三个字母表示行(从下到上1–>4)

The Problem to Make You Happy

Aki

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
bool f[N][N], a[N][N], g[N][N];
vector<pair<int, int> > fromg[N][N], fromf[N][N];
int out[N], cntg[N][N], cntf[N][N];
int main() {
	int T, zzz = 0;
	scanf("%d", &T);
	while (T --) {
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++ i) {
			out[i] = 0;
			for (int j = 1; j <= n; ++ j) {
				fromg[i][j].clear();
				fromf[i][j].clear();
				cntf[i][j] = cntg[i][j] = g[i][j] = f[i][j] = a[i][j] = 0;
			}
		}
		for (int i = 1; i <= m; ++ i) {
			int u, v;
			scanf("%d%d", &u, &v);
			a[u][v] = 1;
			out[u] ++;
		}
		queue<pair<int, int> > q, w;
		for (int x = 1; x <= n; ++ x) {
			for (int y = 1; y <= n; ++ y) {
				if (x == y || out[y] == 0) {
					f[x][y] = 1;
					q.push({x, y});
				}
				if (x == y) {
					g[x][y] = 1;
					w.push({x, y});
				}
				for (int z = 1; z <= n; ++ z) {
					if (a[x][z]) {
						cntg[x][y] ++;
						fromf[z][y].push_back({x, y});
					}
					if (a[y][z]) {
						cntf[x][y] ++;
						fromg[x][z].push_back({x, y});
					}
				}
			}
		}
		while (!q.empty() || !w.empty()) {
			while (!q.empty()) {
				int x = q.front().first, y = q.front().second; q.pop();
				for (auto go : fromf[x][y]) {
					int xx, yy; tie(xx, yy) = go;
					if (!g[xx][yy]) {
						g[xx][yy] = 1;
						w.push({xx, yy});
					}
				}
			}
			while (!w.empty()) {
				int x = w.front().first, y = w.front().second; w.pop();
				for (auto go : fromg[x][y]) {
					int xx, yy; tie(xx, yy) = go;
					if (-- cntf[xx][yy] == 0 && !f[xx][yy]) {
						f[xx][yy] = 1;
						q.push({xx, yy});
					}
				}
			}
		}
		int x, y;
		scanf("%d%d", &y, &x);
		printf("Case #%d: %s\n", ++ zzz, f[x][y] ? "No" : "Yes");
	}
}

Nisiyama

#include <bits/stdc++.h>

int N, M;
std::vector <int> edge[1100];

struct st {
	int loc[2];
	int mv;
	st (int a = 0, int b = 0, int v = 0) {
		loc[0] = a;
		loc[1] = b;
		mv = v;
	}
};

int encode (const st &a) {
	return a.loc[0] * (N + 1) * 2 + a.loc[1] * 2 + a.mv;
}

st decode (int l) {
	return st ((l >> 1) / (N + 1), (l >> 1) % (N + 1), l & 1);
}

int win[2100000], deg[2100000];

int size[1100];

int main () {
	int T;
	scanf ("%d", &T);
	for (int t = 0; t < T; ++t) {
		scanf ("%d%d", &N, &M);
		for (int i = 1; i <= N; ++i) {
			edge[i].clear ();
			size[i] = 0;
		}
		for (int i = 0; i < M; ++i) {
			int u, v;
			scanf ("%d%d", &u, &v);
			edge[v].push_back (u);
			++size[u];
		}
		std::queue <int> q;
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= N; ++j)
				for (int mv = 0; mv < 2; ++mv) {
					if (i == j) {
						q.push (encode (st (i, j, mv)));
						deg[encode (st (i, j, mv))] = 0;
						win[encode (st (i, j, mv))] = (!mv);
					} else if (size[i] == 0 && mv == 0) {
						q.push (encode (st (i, j, mv)));
						deg[encode (st (i, j, mv))] = 0;
						win[encode (st (i, j, mv))] = 0;
					} else if (size[j] == 0 && mv == 1) {
						q.push (encode (st (i, j, mv)));
						deg[encode (st (i, j, mv))] = 0;
						win[encode (st (i, j, mv))] = 0;
					} else {
						deg[encode (st (i, j, mv))] = size[(mv == 0) ? i : j];
						win[encode (st (i, j, mv))] = -1;
					}
				}
		while (!q.empty ()) {
			int d = q.front ();
		   	st s = decode (d);
			q.pop ();
			for (int i = 0; i < edge[s.loc[s.mv ^ 1]].size (); ++i) {
				st ns = s;
				ns.loc[s.mv ^ 1] = edge[s.loc[s.mv ^ 1]][i];
				ns.mv ^= 1;
				int nd = encode (ns);
				if (win[d]) {
					if (--deg[nd] == 0) {
					   win[nd] = 0;
					   q.push (nd);
					}
				} else {
					if (deg[nd] <= 0) continue;
					deg[nd] = 0;
					win[nd] = 1;
					q.push (nd);
				}
			}
		}
		int x, y;
		scanf ("%d%d", &x, &y);
		printf ("Case #%d: ", t + 1);
		if (win[encode (st (y, x, 1))] == 0)
			puts ("No");
		else
			puts ("Yes");
	}
}

lbn187

#include<bits/stdc++.h>
#define N 111
#define CL(a) memset(a,0,sizeof a)
int T,n,m,x,y,ca,i,j,k,l;
bool vs[N][N],e[N][N],ff,f;
int main(){
	scanf("%d",&T);
	for(ca=1;ca<=T;ca++){
		CL(e);CL(vs);
		for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&x,&y),e[x][y]=1;
		for(i=1;i<=n;i++)vs[i][i]=1;
		for(;;){
			for(ff=0,i=1;i<=n;i++)for(j=1;j<=n;j++)if(!vs[i][j]){
				for(f=0,k=1;k<=n&&!f;k++)if(e[i][k]&&k!=j)
					for(f=l=1;l<=n&&f;l++)if(e[j][l])if(vs[k][l]){f=0;break;}
				if(!f)vs[i][j]=1,ff=1;
			}
			if(!ff)break;
		}
		printf("Case #%d: ",ca);
		scanf("%d%d",&x,&y);
		puts(vs[x][y]?"No":"Yes");
	}
}

War Chess