oj.uz

Submission #205094

# Submission time Handle Problem Language Result Execution time Memory
205094 2020-02-27T22:37:07 Z faremy Editor (BOI15_edi) C++14
43 / 100
 132 ms 19188 KB 
#include <iostream>
#include <algorithm>
#include <vector>


const int MAXN = 3e5 + 1;

int type[MAXN];
std::vector<int> state;

std::vector<int> ofRank[MAXN];
int skip[MAXN];
int paired[MAXN];


int jump(int pos)
{
	if (skip[pos] != pos)
		skip[pos] = jump(skip[pos]);
	return skip[pos];
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int ops; std::cin >> ops;
	for (int iOp = 1; iOp <= ops; iOp++)
	{
		std::cin >> type[iOp];
		if (type[iOp] < 0)
			ofRank[-type[iOp]].emplace_back(iOp);
		skip[iOp] = iOp;
	}

	for (int iRank = ops; iRank > 0; iRank--)
		for (int pos : ofRank[iRank])
		{
			if (skip[pos] != pos)
				continue;
			skip[pos] = jump(pos - 1);
			paired[pos] = skip[pos];
			skip[skip[pos]]--;
		}

	state.emplace_back(0);
	for (int iOp = 1; iOp <= ops; iOp++)
	{
		if (type[iOp] > 0)
		{
			state.emplace_back(iOp);
			skip[iOp] = iOp;
		}
		else if (type[paired[iOp]] > 0)
		{
			state.pop_back();
			skip[iOp] = paired[iOp] - 1;
		}
		else
		{
			if (paired[iOp] == 0)
				skip[iOp] = iOp - 1;
			else
				skip[iOp] = paired[iOp];
			int toggle = jump(iOp);

			if (state.back() == toggle)
				state.pop_back();
			else
				state.emplace_back(toggle);
		}

		std::cout << type[state.back()] << '\n';
	}

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 15088 KB Output is correct
2 Correct 75 ms 15088 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 13044 KB Output is correct
2 Correct 66 ms 13680 KB Output is correct
3 Correct 84 ms 14840 KB Output is correct
4 Correct 76 ms 15084 KB Output is correct
5 Correct 132 ms 19188 KB Output is correct
6 Correct 60 ms 12908 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -