oj.uz

Submission #120016

# Submission time Handle Problem Language Result Execution time Memory
120016 2019-06-23T02:53:52 Z E869120 Editor (BOI15_edi) C++14
0 / 100
 3000 ms 18764 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

int N, A[1 << 19];

// ------------------------------------ solve1 ------------------------------
int G[1 << 19], P[1 << 19], level[1 << 19], par[1 << 19], maxlevel = 0;
vector<int>I[1 << 19];
set<int>Set;
priority_queue<int, vector<int>, less<int>> Q;

void init() {
	Set.clear(); while (!Q.empty()) Q.pop(); maxlevel = 0;
	for (int i = 0; i < 109; i++) {
		G[i] = 0; P[i] = 0; level[i] = 0; par[i] = 0; I[i].clear();
	}
}

vector<int> solve1(int NN, vector<int>vec1) {
	init();
	N = NN;
	for (int i = 1; i <= N; i++) A[i] = vec1[i - 1];

	for (int i = 1; i <= N; i++) {
		level[i] = max(0, -A[i]);
		maxlevel = max(maxlevel, level[i]);
	}

	for (int i = N; i >= 1; i--) {
		P[i] = 1;
		for (int j = i + 1; j <= N; j++) {
			if (level[i] < level[j] && par[j] == 0) {
				par[j] = i;
				P[i] ^= P[j];
			}
			if (P[i] == 0) break;
		}
	}

	vector<int>finalans;
	Q.push(0); G[0] = 1;
	for (int i = 1; i <= N; i++) {
		if (A[i] > 0) {
			G[i] = 1; Q.push(i);
		}
		else {
			G[i] = 1; int cx = i;
			while (par[cx] != 0) { cx = par[cx]; G[cx] ^= 1; }
			Q.push(cx);
			while (!Q.empty()) { int pos = Q.top(); if (G[pos] == 0) Q.pop(); else break; }
		}
		int ans = Q.top();
		finalans.push_back(A[ans]);
	}
	return finalans;
}

vector<int> solve2(int NN, vector<int>vec1) {
	init();
	N = NN;
	for (int i = 1; i <= N; i++) A[i] = vec1[i - 1];

	vector<int> finalans;
	for (int i = 1; i <= N; i++) {
		if (A[i] >= 0) {
			P[i] = 1;
		}
		else {
			P[i] = 1;
			for (int j = i - 1; j >= 1; j--) {
				int level = 0; if (A[j] < 0) level = -A[j];
				if (level < -A[i] && P[j] == 1) { par[i] = j; break; }
			}
			int cx = i;
			while (A[cx] < 0) {
				cx = par[cx];
				P[cx] ^= 1;
			}
		}

		int ans = 0;
		for (int j = 1; j <= i; j++) {
			if (P[j] == 1 && A[j] >= 1) ans = A[j];
		}
		finalans.push_back(ans);
	}
	return finalans;
}

vector<int> random_generate(int NN) {
	vector<int>RR; int dep = 0;
	for (int i = 0; i < NN; i++) {
		if (rand() % 2 == 0 || dep == 0) {
			RR.push_back(rand() % 4 + 1); dep++;
		}
		else {
			RR.push_back(-(rand() % 4 + 1)); dep--;
		}
	}
	return RR;
}

int main() {
	int Debug = 1;
	if (Debug == 1) {
		int NN; scanf("%d", &NN);
		vector<int>E(NN, 0);
		for (int i = 0; i < NN; i++) scanf("%d", &E[i]);

		vector<int>F1 = solve1(NN, E);
		for (int i = 0; i < F1.size(); i++) printf("%d\n", F1[i]);
	}
	if (Debug == 2) {
		for (int t = 1; t <= 10000; t++) {
			vector<int> E = random_generate(6);
			vector<int> F1 = solve2(6, E);
			vector<int> F2 = solve1(6, E);

			if (F1 != F2) {
				cout << "Wrong Answer on Test #" << t << endl;
				cout << "Jury = {"; for (int j = 0; j < F1.size(); j++) { if (j) cout << ", "; cout << F1[j]; } cout << "}" << endl;
				cout << "Outp = {"; for (int j = 0; j < F2.size(); j++) { if (j) cout << ", "; cout << F2[j]; } cout << "}" << endl;
				cout << endl;
				cout << N << endl;
				for (int j = 0; j < E.size(); j++) { if (j) cout << " "; cout << E[j]; } cout << endl;
				cout << endl;
			}
		}
	}
	return 0;
}

Compilation message

edi.cpp:8:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
edi.cpp: In function 'int main()':
edi.cpp:117:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < F1.size(); i++) printf("%d\n", F1[i]);
                   ~~^~~~~~~~~~~
edi.cpp:127:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     cout << "Jury = {"; for (int j = 0; j < F1.size(); j++) { if (j) cout << ", "; cout << F1[j]; } cout << "}" << endl;
                                         ~~^~~~~~~~~~~
edi.cpp:128:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     cout << "Outp = {"; for (int j = 0; j < F2.size(); j++) { if (j) cout << ", "; cout << F2[j]; } cout << "}" << endl;
                                         ~~^~~~~~~~~~~
edi.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < E.size(); j++) { if (j) cout << " "; cout << E[j]; } cout << endl;
                     ~~^~~~~~~~~~
edi.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int NN; scanf("%d", &NN);
           ~~~~~^~~~~~~~~~~
edi.cpp:114:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < NN; i++) scanf("%d", &E[i]);
                                ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 18764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3025 ms 15776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

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