oj.uz

답안 #252415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252415 2020-07-25T13:44:34 Z Blagojce Editor (BOI15_edi) C++11
35 / 100
 588 ms 4856 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(a[i] < -1) subtask2 = false;
	}
	if(subtask1){
		brute_force();
	}
	else if(subtask2){
		e1u1();
	}
}

 
int main(){


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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 24 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 43 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 12 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 588 ms 4856 KB Output is correct
2 Correct 581 ms 4856 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 896 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 24 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 43 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 12 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 588 ms 4856 KB Output is correct
11 Correct 581 ms 4856 KB Output is correct
12 Incorrect 16 ms 896 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -