oj.uz

Submission #144180

# Submission time Handle Problem Language Result Execution time Memory
144180 2019-08-16T09:36:45 Z emilem Tenis (COI19_tenis) C++14
39 / 100
 500 ms 13048 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] = {-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();
	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 256 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 Correct 10 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 11 ms 376 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 8 ms 504 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 Correct 10 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 11 ms 376 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 8 ms 504 KB Output is correct
13 Execution timed out 1070 ms 12808 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 10872 KB Output is correct
2 Correct 343 ms 11024 KB Output is correct
3 Correct 323 ms 10996 KB Output is correct
4 Correct 304 ms 11000 KB Output is correct
5 Correct 325 ms 12972 KB Output is correct
6 Correct 317 ms 12920 KB Output is correct
7 Correct 357 ms 13048 KB Output is correct
8 Correct 324 ms 12896 KB Output is correct
9 Correct 336 ms 12868 KB Output is correct
10 Correct 367 ms 12812 KB Output is correct
11 Correct 319 ms 12888 KB Output is correct
12 Correct 325 ms 12920 KB Output is correct
13 Correct 343 ms 13016 KB Output is correct
14 Correct 321 ms 12820 KB Output is correct
15 Correct 322 ms 12792 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 Correct 10 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 11 ms 376 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 8 ms 504 KB Output is correct
13 Execution timed out 1070 ms 12808 KB Time limit exceeded
14 Halted 0 ms 0 KB -