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 | } |