제출 #144174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144174		emilem	Tenis (COI19_tenis)	C++14	7 / 100	1075 ms	7272 KiB

tenis

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int n;
vector<int> ranking[3], rankAt[3];
vector<bool> canWin;

template<typename T>
inline bool Maximize(T& a, T rhs)
{
	if (rhs <= a)
		return false;
	a = rhs;
	return true;
}
void Solve()
{
	fill(canWin.begin(), canWin.end(), false);
	vector<int> prefMax[3][3];
	for (int p1 = 0; p1 < 3; ++p1)
		for (int p2 = 0; p2 < 3; ++p2)
			prefMax[p1][p2] = vector<int>(n);
	for (int i = 0; i < n; ++i)
		for (int p1 = 0; p1 < 3; ++p1)
			for (int p2 = 0; p2 < 3; ++p2)
			{
				prefMax[p1][p2][i] = rankAt[p2][ranking[p1][i]];
				if (i)
					Maximize(prefMax[p1][p2][i], prefMax[p1][p2][i - 1]);
			}
	for (int p = 0; p < 3; ++p)
	{
		int maxAt[3] = {0}; /**/
		for (int i = 0; i < n; ++i)
		{
			// int maxAt[3];
			for (int p1 = 0; p1 < 3; ++p1)
				Maximize(maxAt[p1], prefMax[p][p1][i]); // Maximize???
			while (true)
			{
				bool noUpdate = true;
				for (int p1 = 0; p1 < 3; ++p1)
					for (int p2 = 0; p2 < 3; ++p2)
						if (Maximize(maxAt[p2], prefMax[p1][p2][maxAt[p1]]))
							noUpdate = false;
				if (noUpdate)
					break;
			}
			set<int> losers;
			for (int p1 = 0; p1 < 3; ++p1)
				for (int j = 0; j <= maxAt[p1]; ++j)
					losers.insert(ranking[p1][j]);
			if (losers.size() == n)
			{
				for (int j = i; j < n; ++j)
				// for (int j = 0; j <= i; ++j)
					canWin[ranking[p][j]] = true;
				break;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int q;
	cin >> n >> q;
	canWin.resize(n);
	ranking[0] = ranking[1] = ranking[2] = vector<int>(n);
	rankAt[0] = rankAt[1] = rankAt[2] = vector<int>(n);
	for (int p = 0; p < 3; ++p)
		for (int i = n - 1; i >= 0; --i)
		// for (int i = 0; i < n; ++i)
		{
			cin >> ranking[p][i];
			--ranking[p][i];
			rankAt[p][ranking[p][i]] = i;
		}
	Solve();
	while (q--)
	{
		int type;
		cin >> type;
		if (type == 1)
		{
			int nephew;
			cin >> nephew; --nephew;
			cout << (canWin[nephew] ? "DA\n" : "NE\n");
		}
		else
		{
			int p, a, b;
			cin >> p >> a >> b; --p; --a; --b;
			swap(ranking[p][rankAt[p][a]], ranking[p][rankAt[p][b]]);
			for (int p = 0; p < 3; ++p)
				for (int i = n - 1; i >= 0; --i)
					rankAt[p][ranking[p][i]] = i;
			Solve();
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

tenis.cpp: In function 'void Solve()':
tenis.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (losers.size() == n)
        ~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49