oj.uz

Submission #144193

# Submission time Handle Problem Language Result Execution time Memory
144193 2019-08-16T09:51:27 Z emilem Tenis (COI19_tenis) C++14
39 / 100
 500 ms 11128 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();
	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

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 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct

Subtask #2
11.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 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4 ms 504 KB Output is correct

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 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Execution timed out 865 ms 10940 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 10916 KB Output is correct
2 Correct 331 ms 11128 KB Output is correct
3 Correct 319 ms 11044 KB Output is correct
4 Correct 335 ms 10872 KB Output is correct
5 Correct 351 ms 11000 KB Output is correct
6 Correct 324 ms 11036 KB Output is correct
7 Correct 332 ms 11000 KB Output is correct
8 Correct 310 ms 10872 KB Output is correct
9 Correct 334 ms 10952 KB Output is correct
10 Correct 334 ms 10972 KB Output is correct
11 Correct 316 ms 11004 KB Output is correct
12 Correct 325 ms 10872 KB Output is correct
13 Correct 371 ms 10980 KB Output is correct
14 Correct 320 ms 10872 KB Output is correct
15 Correct 328 ms 11000 KB Output is correct

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 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Execution timed out 865 ms 10940 KB Time limit exceeded
14 Halted 0 ms 0 KB -