oj.uz

Submission #144172

# Submission time Handle Problem Language Result Execution time Memory
144172 2019-08-16T09:24:36 Z emilem Tenis (COI19_tenis) C++14
0 / 100
 62 ms 12400 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)
		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();
		}
	}
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 12400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -