oj.uz

Submission #144179

# Submission time Handle Problem Language Result Execution time Memory
144179 2019-08-16T09:35:50 Z emilem Tenis (COI19_tenis) C++14
7 / 100
 500 ms 7112 KB 
#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}; /**/
		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();
	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();
		}
	}

	char I;
	cin >> I;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Execution timed out 1074 ms 376 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Execution timed out 1074 ms 376 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 7112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Execution timed out 1074 ms 376 KB Time limit exceeded
8 Halted 0 ms 0 KB -