Luogu p2482 [sdoi2010] zhuguosha

#include<bits/stdc++.h>

using namespace std;
const int N = 20;
vector<char> P;// Deck 

int n, m, f;
int nxt[N], lst[N];

struct Pig {
    
	string name;// True identity 
	/*  Main pig :MP  Zhongzhu :ZP  Anti pig :FP */
	vector<char> p;
	int hp;// Blood volume 
	int z;// Whether to install a crossbow 
	int t;// Superficial identity 
	/*  Unknown :0  Zhongzhu :1（ The main pig is loyal by default from the beginning ）  Anti pig :2  Anti pig like :3 */
	void throwcard(int& x) {
    // Discard the second x card 
		p.erase(p.begin() + x);
		x--;
	}
	int search(char c) {
    // Find the first one as c The card of , And discard 
		for (int i = 0; i < p.size(); i++) {
    
			if (p[i] == c) {
    
				throwcard(i);
				return 1;// Found return 1
			}
		}
		return 0;// No return found 0
	}
	void getcard(int x) {
    // Touch from the deck x card 
		while (x--) {
    
			char c = P.front();
			p.push_back(c);
			P.erase(P.begin());
			if (P.empty()) P.push_back(c);
			// If there are not enough cards in the stack , Always touch the last card 
		}
	}
}a[N];
// Game over 
void end() {
    
	if (a[1].hp == 0) cout << "FP" << endl;
	else cout << "MP" << endl;
	for (int i = 1; i <= n; i++) {
    
		if (a[i].hp == 0) cout << "DEAD" << endl;
		else {
    
			int len = a[i].p.size();
			for (int j = 0; j < len; j++)
				cout << a[i].p[j] << " ";
			cout << endl;
		}
	}
	exit(0);
}
// Judge x Can it be right? y Show hostility 
int hostility(int x, int y) {
    
	//x It's the main pig and y It's anti pig or anti pig 
	if (a[x].name == "MP" && (a[y].t == 2 || a[y].t == 3))
		return 1;
	//x It's a loyal pig and y It's anti pig 
	if (a[x].name == "ZP" && a[y].t == 2)
		return 1;
	//x It's anti pig and y It's Zhongzhu 
	if (a[x].name == "FP" && a[y].t == 1)
		return 1;
	return 0;
}
// Judge x Can it be right? y Be courteous 
int squire(int x, int y) {
    
	//x It's the main pig and y It's Zhongzhu 
	if (a[x].name == "MP" && a[y].t == 1)
		return 1;
	//x It's a loyal pig and y It's Zhongzhu 
	if (a[x].name == "ZP" && a[y].t == 1)
		return 1;
	//x It's anti pig and y It's anti pig 
	if (a[x].name == "FP" && a[y].t == 2)
		return 1;
	return 0;
}
//x Killed y
void killed(int x, int y) {
    
	if (a[y].name == "MP") end();// Judge y Is it the main pig 
	if (a[y].name == "FP") {
    
		f--;
		if (f == 0) end();// There is no anti pig. The game is over 
		a[x].getcard(3);// Touch three cards 
	}
	else if (a[y].name == "ZP" && a[x].name == "MP") {
    // If the main pig kills the loyal pig 
		a[x].p.clear();// Empty the main pig Library 
		a[x].z = 0;// Weapons should also be emptied 
	}
	nxt[lst[y]] = nxt[y];
	lst[nxt[y]] = lst[y];
}
//x Attack for the source of damage y
void attack(int x, int y) {
    
	a[y].hp--;
	if (a[y].hp == 0) {
    // Blood volume is 0
		int t = a[y].search('P');// Eat peaches 
		if (t == 0) killed(x, y);
		else a[y].hp++;
	}
}
// With no chink in one's armour , Successfully returns 1, Failure to return 0

int Impeccable(int s, int x) {
    
	for (int i = s, j = 0; !j || i != s; i = nxt[i], j = 1) {
    
		int t;
		if (x == 0) t = hostility(i, s);
		else t = squire(i, x);
		// If x by 0 explain s It's the last time you used it, it's impeccable , Otherwise, explain s Yes x Use 
		if (t && a[i].search('J')) {
    
			if (a[i].name == "FP") a[i].t = 2;
			else a[i].t = 1;
			return !Impeccable(i, 0);
		}
	}
	return 0;
}

int main() {
    
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
    
		string s;
		cin >> s;
		a[i].name = s;
		if (s[0] == 'F') f++;
		for (int j = 0; j < 4; j++) {
    
			char c;
			cin >> c;
			a[i].p.push_back(c);
		}
		nxt[i] = i + 1, lst[i] = i - 1;
		a[i].hp = 4;
		a[i].z = a[i].t = 0;
	}
	for (int i = 0; i < m; i++) {
    
		char c;
		cin >> c;
		P.push_back(c);
	}
	nxt[n] = 1, lst[1] = n;
	int now = 1;
	a[1].t = 1;// The main pig defaults to loyal pig 
	if (f == 0) end();
	while (true) {
    
		int kill = 0;// Have you ever used killing 
		a[now].getcard(2);// Touch two cards 
		for (int i = 0; i < a[now].p.size() && a[now].hp; i++) {
    
			if (a[now].p[i] == 'Z') {
    // Crossbow 
				a[now].z = 1;
				a[now].throwcard(i);
				i = -1;// Start all over again , Because you may be able to use the previous kill 
			}
			else if (a[now].p[i] == 'P') {
    // peach 
				if (a[now].hp == 4) continue;// Don't eat blood 
				a[now].hp++;
				a[now].throwcard(i);
			}
			else if (a[now].p[i] == 'K') {
    
				if (a[now].z || kill == 0) {
    // If equipped with a crossbow or not used to kill 
					int t = nxt[now];//now The next pig 
					if (hostility(now, t)) {
    // Judge whether it can show hostility 
						if (a[now].name == "FP") a[now].t = 2;
						else a[now].t = 1;
						a[now].throwcard(i);
						kill = 1;
						if (!a[t].search('D')) attack(now, t);
					}
				}
			}
			else if (a[now].p[i] == 'F') {
    // duel 
				int j;
				if (a[now].name == "FP") j = 1;// Anti pig duel is used against the main pig 
				else j = nxt[now];
				for (; j != now; j = nxt[j]) {
    
					if (hostility(now, j)) {
    
						a[now].throwcard(i);
						if (a[now].name == "FP") a[now].t = 2;
						else a[now].t = 1;
						if (Impeccable(now, j)) break;
						if (a[j].name == "ZP" && a[now].name == "MP") {
    
							attack(now, j);
							break;
						}
						int t = 1;
						while (true) {
    
							if (t & 1) {
    
								if (!a[j].search('K')) {
    
									attack(now, j);
									break;
								}
							}
							else {
    
								if (!a[now].search('K')) {
    
									attack(j, now);
									i = max(-1, i - 1);
									break;
								}
							}
							t ^= 1;
						}
						i = -1;
						// The duel may make some pigs clear , Start from scratch 
						break;
					}
				}
			}
			else if (a[now].p[i] == 'N' || a[now].p[i] == 'W') {
    
				char c = a[now].p[i], d;
				if (c == 'N') d = 'K';
				else d = 'D';
				a[now].throwcard(i);
				for (int j = nxt[now]; j != now; j = nxt[j]) {
    
					if (!Impeccable(now, j) && !a[j].search(d)) {
    
						// Attacked the main pig , Become anti pig 
						if (a[j].name == "MP" && a[now].t == 0) a[now].t = 3;
						attack(now, j);
					}
				}
				i = -1;
			}
		}
		now = nxt[now];
	}
	return 0;
}
/* 2 1 MP K K D J FP W N D N K 3 5 MP F K D J FP J F Z K FP Z W Z P J N P N N */