SHOW:
|
|
- or go back to the newest paste.
1 | #include<fstream> | |
2 | #include<vector> | |
3 | #include<algorithm> | |
4 | #include<stack> | |
5 | using namespace std; | |
6 | - | /* |
6 | + | |
7 | ifstream in("solar.in"); | |
8 | ofstream out("solar.out"); | |
9 | - | */ |
9 | + | |
10 | //declare stacks and N and some other variables to check wheather the first | |
11 | // of the last value fits out criteria | |
12 | int N; | |
13 | stack<int>max_from_startpoint; | |
14 | stack<int> values; | |
15 | int max_val,min_val; | |
16 | int first_val=0,last_val=-1; | |
17 | ||
18 | void Read_and_find_mins_to_here(){ | |
19 | in>>N; | |
20 | //read the values and find the minimun one up to a certain point | |
21 | for(int i=0; i<N; i++){ | |
22 | int val; | |
23 | in>>val; | |
24 | if(i==0){ | |
25 | max_from_startpoint.push(val); | |
26 | values.push(val); | |
27 | min_val=max_val=val; | |
28 | } | |
29 | else{ | |
30 | int curmax=max(max_from_startpoint.top(),values.top()); | |
31 | max_from_startpoint.push(curmax); | |
32 | values.push(val); | |
33 | //den xreiazetai na alla3w tin timi toy afoy den 8a to 3anaxrisimopoiisw | |
34 | if(val<min_val){ | |
35 | first_val=-1; | |
36 | } | |
37 | if(val>max_val){ | |
38 | max_val=val; | |
39 | if(i==N-1){ | |
40 | last_val=0; | |
41 | } | |
42 | } | |
43 | } | |
44 | } | |
45 | } | |
46 | ||
47 | //run through the two stacks to find max values up | |
48 | //to a certain point and then check if the values.top() | |
49 | //satisfies the given condition | |
50 | void Find_solution(){ | |
51 | //prwta elegxw to last_val | |
52 | if(last_val==0){ | |
53 | out<<max_val<<'\n'; | |
54 | return; | |
55 | } | |
56 | //meta ta eswterika | |
57 | int minc=values.top(); | |
58 | int minprev=minc; | |
59 | values.pop(); | |
60 | max_from_startpoint.pop(); | |
61 | while(!values.empty()){ | |
62 | minc=min(values.top(),minc); | |
63 | //out<<values.top()<<' '<<minprev<<' '<<max_from_startpoint.top()<<'\n'; | |
64 | if(minprev>values.top() && max_from_startpoint.top()<values.top()){ | |
65 | out<<values.top(); | |
66 | break; | |
67 | } | |
68 | minprev=minc; | |
69 | values.pop(); | |
70 | max_from_startpoint.pop(); | |
71 | } | |
72 | if(values.empty()){ | |
73 | //kai an den exw brei kati mexri edw elegxw kai to first_val | |
74 | if(first_val==0){ | |
75 | out<<min_val<<'\n'; | |
76 | return; | |
77 | } | |
78 | out<<"NOT FOUND"; | |
79 | } | |
80 | } | |
81 | ||
82 | int main(){ | |
83 | Read_and_find_mins_to_here(); | |
84 | Find_solution(); | |
85 | return 0; | |
86 | } |