oj.uz

Submission #252412

# Submission time Handle Problem Language Result Execution time Memory
252412 2020-07-25T13:42:47 Z Blagojce Editor (BOI15_edi) C++11
35 / 100
 605 ms 6136 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e5;


int n;

int a[mxn];

void brute_force(){
	bool ok[n];
	memset(ok, false, sizeof(ok));
	int ans = -1;
	
	int pr[n];
	memset(pr, -1, sizeof(pr));
	
	fr(i, 0, n){
		ok[i] = true;
		if(a[i] > 0){
			ans = i;
		}
		else{
			int pos = i;
			for(int j = i-1; j >= 0; j --){
				if(!ok[j]) continue;
				if(a[j] > 0){
					pr[pos] = j;
					ok[j] = false;
					break;
				} 
				else if(a[j] > a[pos]){
					pr[pos] = j;
					ok[j] = false;
					
					if(pr[j] == -1){
						break;
					}
					else{
						pos = pr[j];
						pr[j] = -1;
						
						ok[pos] = true;
						j = pos;		
						if(a[pos] >0) break;
					}
				}
			}
		}
		ans = i;
		while(ans >= 0 && (!ok[ans] || a[ans] < 0)){
			--ans;
		} 
		
		if(ans == -1){
			cout<<0<<endl;
		}
		else{
			cout<<a[ans] << endl;
		}
	}
}
void e1u1(){
	int pr[n];
	memset(pr, -1, sizeof(pr));
	int ans = -1;
	fr(i, 0, n){
		
		if(a[i] < 0){
			if(ans != -1){
				ans = pr[ans];
			}
		}
		else{
			pr[i] = ans;
			ans = i;
			
		}
		
		if(ans == -1) cout<<0<<endl;
		else cout<<a[ans]<<endl;
	}

}

void solve(){
	cin >> n;
	bool subtask1 = n<=5000;
	bool subtask2 = true;
	fr(i, 0, n){
		cin >> a[i];
		if(abs(a[i]) > 1) subtask2 = false;
	}
	if(subtask1){
		brute_force();
	}else e1u1();
	
}

 
int main(){


	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Compilation message

edi.cpp: In function 'void solve()':
edi.cpp:110:7: warning: variable 'subtask2' set but not used [-Wunused-but-set-variable]
  bool subtask2 = true;
       ^~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 25 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 41 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 11 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 4836 KB Output is correct
2 Correct 605 ms 6136 KB Output is correct

Subtask #3
0 / 28.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 25 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 41 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 11 ms 384 KB Output is correct
10 Correct 594 ms 4836 KB Output is correct
11 Correct 605 ms 6136 KB Output is correct
12 Incorrect 294 ms 2424 KB Output isn't correct
13 Halted 0 ms 0 KB -