AM51's blog

By AM51, 11 years ago, In English

http://codeforces.net/contest/294/problem/E

explaination for this problem is not present in the editorial so can anyone help me with this problem

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By AM51, 11 years ago, In English

output is coming correct on ideone but not on codeforces for the problem http://codeforces.net/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;
}

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

By AM51, 11 years ago, In English

http://codeforces.net/contest/281/problem/D

can somebody suggest an approach to this problem

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By AM51, 11 years ago, In English

http://codeforces.net/contest/272/problem/D

can somebody point out mistake in my code getting WA for case 2 1 2 2 2 4

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb(x) push_back(x)
#define S(x) scanf("%d",&x)
#define Sl(x) scanf("%lld",&x)
#define M(x,i) memset(x,i,sizeof(x))
#define F(i,a,n) for(i=(a);i<(n);++i)
#define FD(i,a,n) for(i=(a);i>=(n);--i)
using namespace std;
map<int,int> mp;
int a[100005];
int b[100005];
ll fact[200005];
int MOD=1;
ll modm(ll a,ll b)
{
	return (a*b)%MOD;
}
void pre()
{
	int i;
	fact[0]=1;
	F(i,1,200005){
		fact[i]=modm(fact[i-1],(ll)i);
	}
}
int fi(int n) 
{ 
	int result = n; 
	for(int i=2;i*i <= n;i++) 
	{ 
		if (n % i == 0) result -= result / i; 
		while (n % i == 0) n /= i; 
	} 
	if (n > 1) result -= result / n; 
	return result; 
} 
unsigned long long modPow(unsigned long long x,unsigned long long y)
{
	unsigned long long r=1, a=x;
	while (y > 0) {
		if ( (y&1)==1 ) {
			r = (r * a) % MOD;
		}
		a = (a * a) % MOD;
		y /= 2;
	}

	return r;
}
// Modular multiplicative inverse through Fermat's little theorem:
unsigned long long modInverse(long x,int y)
{
	return modPow(x, y-1);
}
int main()
{
	int n,i,cnt=0;
	ll ans1,ans2;
	S(n);
	F(i,0,n){
		S(a[i]);
		mp[a[i]]++;
	}
	F(i,0,n){
		S(b[i]);
		mp[b[i]]++;
	}

	S(MOD);
	pre();

	F(i,0,n){
		if(a[i]==b[i]){
			cnt++;
		}
	}

	ans1=modPow(2,cnt);
	ans2=1;
	map<int,int> ::iterator it;
	for(it=mp.begin();it!=mp.end();it++){
		//cout<<(*it).first<<" "<<(*it).second<<" "<<fact[(*it).second]<<endl;
		ans2=modm(ans2,fact[(*it).second]);
	}

	if(ans1==0)ans1=1;
        if(ans2==0)ans2=1;
	cout<<modm(ans2,modInverse(ans1,fi(MOD)))<<endl;

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By AM51, 11 years ago, In English

http://codeforces.net/contest/261/problem/B can somebody explain the dp solution of this problem as the editorial is not very clear

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it