oj.uz

Submission #234080

# Submission time Handle Problem Language Result Execution time Memory
234080 2020-05-22T23:44:55 Z hugo_pm Fish (IOI08_fish) C++17
0 / 100
 108 ms 23752 KB 
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using ll = long long;

using PQ = vector<int>; 
const int maxElem = 3e5 + 5;
PQ hidden[maxElem];
int level[maxElem];
int lastEdit[maxElem];
int parent[maxElem];
int nbElem;

bool comp(const int &a, const int &b) {
	return level[a] < level[b];
}

void merge(PQ &dest, PQ &eaten) {
	if (dest.size() < eaten.size()) swap(dest, eaten); 
	if (dest.size() < 4U*eaten.size()) {
		dest.insert(dest.end(), eaten.begin(), eaten.end());
		make_heap(dest.begin(), dest.end(), comp);
		return;
	}
	for (int x : eaten) {
		dest.push_back(x);
		push_heap(dest.begin(), dest.end(), comp);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> nbElem;	
	for (int iElem = 1; iElem <= nbElem; ++iElem) {
		cin >> lastEdit[iElem];
		level[iElem] = max(0, -lastEdit[iElem]);
	}

	PQ cur;
	for (int iElem = nbElem; iElem >= 1; --iElem) {
		PQ nxt;
		while (!cur.empty() && level[cur.front()] > level[iElem]) {
			parent[cur.front()] = iElem-1;
			merge(nxt, hidden[cur.front()]);
			pop_heap(cur.begin(), cur.end(), comp);
			cur.pop_back();
		}
		nxt.push_back(iElem);
		push_heap(nxt.begin(), nxt.end(), comp);
		merge(hidden[iElem], cur);
		cur.swap(nxt);
	}

	for (int iElem = 1; iElem <= nbElem; ++iElem) {
		if (level[iElem] > 0) {
			lastEdit[iElem] = lastEdit[parent[iElem]];
		}
		cout << lastEdit[iElem] << "\n";
	}
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7680 KB Output isn't correct

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 22964 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 23288 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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