Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define dbg(i,j) cout<<"I am "<<i<<" = "<<endl<<j<<endl;
- #define dbr(name,a) cout<<name<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
- #define DBR(name,a) cout<<name<<endl;for(auto x:a){ for(auto y:x)cout<<y<<" ";cout<<endl;}
- #define dbmp(name,a) cout<<name<<endl;for(auto x:a){ cout<<x.first<<"\t"<<x.second<<endl;}
- #define dbp(name,a) cout<<name<<endl;cout<<a.first<<"\t"<<a.second<<endl;
- #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- using namespace std;
- typedef long long int big;
- typedef long double fig;
- big arr[1000007];
- big element(big n,big i,big position){
- big start=i;
- big end=n-1;
- big index=position-1;
- if(index<=(end-start)){
- return arr[index+i];
- }
- else{
- return arr[(index-(end-start+1))*2];
- }
- }
- big damage(big n,big i){
- big size=ceil((double)i/(double)(2.0))+(n-i);
- big d=0;
- if(i%2!=0){
- d=d-arr[i-1];
- }
- big position=size;
- big step=2;
- while(position!=1){
- if((position-1)%step==0){
- d=d-element(n,i,position);
- }
- else{
- position=((position-1)-(position-1)%step)+1;
- }
- step=step*2;
- }
- return d;
- }
- int main(){
- //boost;
- big t;
- scanf("%lld",&t);
- while(t--){
- big n;
- scanf("%lld",&n);
- n--;
- for(big i=0;i<n;i++){
- scanf("%lld",&arr[i]);
- }
- big f;
- scanf("%lld",&f);
- big hack=(n-(1<<(big)(floorl(log2((double)(n))))));
- if(arr[hack*2]<=f){
- printf("possible\n");
- printf("%lld %lld\n",hack*2+1,f);
- continue;
- }
- else{
- vector<pair<big,big>> result;
- for(big i=0;i<n;i++){
- if(arr[i]<=f){
- result.push_back(make_pair(damage(n,i),-i));
- }
- }
- if(result.size()!=0){
- printf("possible\n");
- printf("%lld %lld\n",abs((*max_element(result.begin(),result.end())).second)+1,abs((*max_element(result.begin(),result.end())).first)+f);
- }
- else{
- printf("impossible\n");
- }
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment