Advertisement
dimtsitselas

Untitled

Mar 9th, 2014
714
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<fstream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<stack>
  5. using namespace std;
  6.  
  7. ifstream in("solar.in");
  8. ofstream out("solar.out");
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement