zereff's blog

By zereff, history, 4 weeks ago, In English

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.

Problem link : https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d12d7

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;

        }
    }
}
 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zereff (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zereff (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zereff (previous revision, new revision, compare).