Submission #144193

#	Time	Username	Problem	Language	Result	Execution time	Memory
144193		emilem	Tenis (COI19_tenis)	C++14	39 / 100	865 ms	11128 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] = {-1, -1, -1}; /**/
		set<int> losers;
		for (int i = 0; i < n; ++i)
		{
			// int maxAt[3];
			for (int p1 = 0; p1 < 3; ++p1)
			{
				int temp = prefMax[p][p1][i];
				if (temp > maxAt[p1])
				{
					for (int j = maxAt[p1] + 1; j <= temp; ++j)
						losers.insert(ranking[p1][j]);
					maxAt[p1] = temp;
				}
			}
			while (true)
			{
				bool noUpdate = true;
				for (int p1 = 0; p1 < 3; ++p1)
					for (int p2 = 0; p2 < 3; ++p2)
					{
						int temp = prefMax[p1][p2][maxAt[p1]];
						if (temp > maxAt[p2])
						{
							for (int j = maxAt[p2] + 1; j <= temp; ++j)
								losers.insert(ranking[p2][j]);
							maxAt[p2] = temp;
							noUpdate = false;
						}
					}
				if (noUpdate)
					break;
			}
			/*
			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();
	struct Update
	{
		Update(int p_, int a_, int b_)
			: p(p_)
			, a(a_)
			, b(b_)
		{}

		int p, a, b;
	};
	vector<Update> upds;
	bool mustUpdate = true;
	while (q--)
	{
		int type;
		cin >> type;
		if (type == 1)
		{
			if (mustUpdate)
			{
				for (auto upd = upds.begin(); upd != upds.end(); ++upd)
				{
					swap(ranking[upd->p][rankAt[upd->p][upd->a]], ranking[upd->p][rankAt[upd->p][upd->b]]);
					swap(rankAt[upd->p][upd->a], rankAt[upd->p][upd->b]);
					/*
					for (int p = 0; p < 3; ++p)
						for (int i = n - 1; i >= 0; --i)
							rankAt[p][ranking[p][i]] = i;
					*/
				}
				Solve();
				upds.clear();
				mustUpdate = false;
			}
			int nephew;
			cin >> nephew; --nephew;
			cout << (canWin[nephew] ? "DA\n" : "NE\n");
		}
		else
		{
			int p, a, b;
			cin >> p >> a >> b; --p; --a; --b;
			upds.push_back(Update(p, a, b));
			mustUpdate = true;
			/*
			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();
			*/
		}
	}

	char I;
	cin >> I;
}

Compilation message (stderr)

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

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