AM51's blog

output incorrect on codeforces
By AM51, 10 years ago, In English

output is coming correct on ideone but not on codeforces for the problem http://codeforces.com/contest/282/problem/E http://ideone.com/VFBY1G

#include<bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
typedef long long LL;
typedef struct ll
{
    int leftc; // number of prefixes that end towards left
    int rightc;//number of prefixes ending towards right
    struct ll * left;
    struct ll * right;
}node;
node * insert(node * root,long long n, int level)
{
    if(level==-1)return root;
    long long x=((n>>level)&1);
    if(x)
    {
        root->rightc++;
        if(root->right==NULL)
        {
            root->right=(node *)malloc(sizeof(node));
            root->right->leftc=root->right->rightc=0;
        }
        root->right=insert(root->right,n,level-1);
    }
    else
    {
        root->leftc++;
        if(root->left==NULL)
        {
            root->left=(node *)malloc(sizeof(node));
            root->left->leftc=root->left->rightc=0;
        }
        root->left=insert(root->left,n,level-1);
    }
    return root;
}
long long arr[50];
long long query( node * root,long long  n, int level)
{
    if(level==-1 || root==NULL)return 0LL;
    long long int p=((n>>level)&1);
    if(p){
	if(root->left!=NULL){	
		return query(root->left,n,level-1);
	} else {
		return query(root->right,n,level-1)+arr[level];
	}
    } else {
	if(root->right!=NULL){	
		return query(root->right,n,level-1)+arr[level];
	} else {
		return query(root->left,n,level-1);
	}
    }
}
node* remove(node *root,long long n,int level)
{
		if(level==-1 || root==NULL)return root;
		if (n >> level & 1)
		{
			root->rightc--;
			remove(root->right,n,level-1);
			if (root->rightc==0) root->right = NULL;
		}
		else
		{
			root->leftc--;
			remove(root->left,n,level-1);
			if (root->leftc==0) root->left = NULL;
		}
		return root;
}
long long a[100005];
int main()
{
     int i,n;
     long long int val,xx,ans=0;
     node * root;
     root=(node *)malloc(sizeof(node));
     root->left=root->right=NULL;
     root->leftc=root->rightc=0;
     arr[0]=1;
     for(i=1;i<41;i++){
	     arr[i]=arr[i-1]*2;
     }
     //cout<<arr[40]<<endl;
    cin>>n;
    xx=0;
    for(i=0;i<n;i++){
		cin>>a[i];
		xx=xx^a[i];
		root=insert(root,xx,40);
    }

	//cout<<root->rightc<<" "<<root->leftc<<endl;
    xx=0;
   for(i=n-1;i>=0;i--){
     xx^=a[i];
     root=remove(root,a[i],40);
     val=query(root,xx,40);
    //cout<<xx<<" "<<val<<endl;
     ans=max(ans,xx^val);
     }

   cout<<ans<<endl;
}
  • Vote: I like it
  • -19
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

simple case like like 2 1 2 is also failing on codeforces can somebody point out the mistake i am using trie for applying addition and removing operations

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that your trouble caused because of dynamic allocations.

At least, I feel this code not OK:

root->right=(node *)malloc(sizeof(node));
root->right->leftc=root->right->rightc=0;

What is the value of root->right->left and root->right->right? They are not initialized. malloc function doesn't clear the memory allocated. You may need to use calloc. But the following code is better:

struct node {
  int SomeData;
  node *Left, *Right, *Parent;
};

node* root;
main (){
  root = new node();
  ...
}

PS: Your trie code is too long, you may need to reduce its length.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ya the problem was with malloc got ac thanx

    → Reply