==================↵
Following is the code I submitted for question 3 after contest. for all the vectors created by my code I tested them with the first question code. It passed on all the combinations but codejam gave WA. ↵
I would be very thankful if someone can point out the mistake.↵
------------------↵
==================↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define MOD 1000000007↵
#define N 100000 //array size↵
int main(){↵
int testcases,it=1;↵
cin>>testcases;↵
while(it<=testcases){↵
↵
int n,c;↵
cin>>n>>c;↵
vector<ll> vec(n,0);↵
cout<<"Case #"<<it<<":"; it++;↵
if(c < n-1 || c> (n*(n+1)/2-1)){↵
cout<<" IMPOSSIBLE\n";}↵
else{↵
ll val = 1,curr=0,d=-99,sig=-1;↵
c= c-n+1;↵
int j;↵
for(j=1;j<n;j++){↵
val = 1+max(0,min(n-j,c));↵
c= c-(n-j);↵
if(d==1 && val ==1){↵
↵
while(curr >= 0 && curr <n && vec[curr]!=0) curr+=sig;↵
if(curr<0 || vec[curr]!=0 ){↵
if(sig==-1) sig =1;↵
else sig =-1;↵
while(vec[curr]!=0) curr+=sig;↵
}↵
vec[curr]=j;↵
}↵
else if(j%2==0){↵
vec[curr-val-1]=j;↵
curr-=val;↵
sig=-1;↵
}else{↵
vec[curr+val-1]=j;↵
curr+=val; ↵
sig =1;↵
}↵
d=val;↵
}↵
for(ll i=0;i<n;i++){↵
if(vec[i]==0){↵
vec[i]=n;↵
}↵
cout<<" "<<vec[i];↵
}↵
vec.clear();↵
cout<<endl;↵
↵
}↵
}↵
}~~↵
Following is the code I submitted for question 3 after contest. for all the vectors created by my code I tested them with the first question code. It passed on all the combinations but codejam gave WA. ↵
I would be very thankful if someone can point out the mistake.↵
==================↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define MOD 1000000007↵
#define N 100000 //array size↵
int main(){↵
int testcases,it=1;↵
cin>>testcases;↵
while(it<=testcases){↵
↵
int n,c;↵
cin>>n>>c;↵
vector<ll> vec(n,0);↵
cout<<"Case #"<<it<<":"; it++;↵
if(c < n-1 || c> (n*(n+1)/2-1)){↵
cout<<" IMPOSSIBLE\n";}↵
else{↵
ll val = 1,curr=0,d=-99,sig=-1;↵
c= c-n+1;↵
int j;↵
for(j=1;j<n;j++){↵
val = 1+max(0,min(n-j,c));↵
c= c-(n-j);↵
if(d==1 && val ==1){↵
↵
while(curr >= 0 && curr <n && vec[curr]!=0) curr+=sig;↵
if(curr<0 || vec[curr]!=0 ){↵
if(sig==-1) sig =1;↵
else sig =-1;↵
while(vec[curr]!=0) curr+=sig;↵
}↵
vec[curr]=j;↵
}↵
else if(j%2==0){↵
vec[curr-val-1]=j;↵
curr-=val;↵
sig=-1;↵
}else{↵
vec[curr+val-1]=j;↵
curr+=val; ↵
sig =1;↵
}↵
d=val;↵
}↵
for(ll i=0;i<n;i++){↵
if(vec[i]==0){↵
vec[i]=n;↵
}↵
cout<<" "<<vec[i];↵
}↵
vec.clear();↵
cout<<endl;↵
↵
}↵
}↵
}~~↵
