Knobody

Untitled

Sep 22nd, 2019
544
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define dbg(i,j) cout<<"I am "<<i<<" = "<<endl<<j<<endl;
  3. #define dbr(name,a) cout<<name<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
  4. #define DBR(name,a) cout<<name<<endl;for(auto x:a){ for(auto y:x)cout<<y<<" ";cout<<endl;}
  5. #define dbmp(name,a) cout<<name<<endl;for(auto x:a){ cout<<x.first<<"\t"<<x.second<<endl;}
  6. #define dbp(name,a) cout<<name<<endl;cout<<a.first<<"\t"<<a.second<<endl;
  7. #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  8. using namespace std;
  9.  
  10. typedef long long int big;
  11.  
  12. typedef  long double fig;
  13.  
  14.  
  15. big arr[1000007];
  16.  
  17.  
  18. big element(big n,big i,big position){
  19.     big start=i;
  20.     big end=n-1;
  21.     big index=position-1;
  22.     if(index<=(end-start)){
  23.         return arr[index+i];
  24.     }
  25.     else{
  26.         return arr[(index-(end-start+1))*2];
  27.     }
  28. }
  29.  
  30.  
  31. big damage(big n,big i){
  32.     big size=ceil((double)i/(double)(2.0))+(n-i);
  33.     big d=0;
  34.     if(i%2!=0){
  35.         d=d-arr[i-1];
  36.     }
  37.    
  38.     big position=size;
  39.     big step=2;
  40.     while(position!=1){
  41.         if((position-1)%step==0){
  42.             d=d-element(n,i,position);
  43.         }
  44.         else{
  45.             position=((position-1)-(position-1)%step)+1;
  46.         }
  47.         step=step*2;
  48.     }
  49.    
  50.     return d;
  51. }
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. int main(){
  59.     //boost;
  60.     big t;
  61.     scanf("%lld",&t);
  62.     while(t--){
  63.         big n;
  64.         scanf("%lld",&n);
  65.         n--;
  66.         for(big i=0;i<n;i++){
  67.             scanf("%lld",&arr[i]);
  68.         }
  69.         big f;
  70.         scanf("%lld",&f);
  71.         big hack=(n-(1<<(big)(floorl(log2((double)(n))))));
  72.         if(arr[hack*2]<=f){
  73.             printf("possible\n");
  74.             printf("%lld %lld\n",hack*2+1,f);
  75.             continue;
  76.         }
  77.         else{
  78.             vector<pair<big,big>> result;
  79.             for(big i=0;i<n;i++){
  80.                 if(arr[i]<=f){
  81.                     result.push_back(make_pair(damage(n,i),-i));
  82.                 }
  83.             }
  84.             if(result.size()!=0){
  85.                 printf("possible\n");
  86.                 printf("%lld %lld\n",abs((*max_element(result.begin(),result.end())).second)+1,abs((*max_element(result.begin(),result.end())).first)+f);
  87.             }
  88.             else{
  89.                 printf("impossible\n");
  90.             }
  91.         }
  92.     }
  93.     return 0;
  94. }
Add Comment
Please, Sign In to add comment