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
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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
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;
}
http://codeforces.net/contest/281/problem/D
can somebody suggest an approach to this problem
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;
http://codeforces.net/contest/261/problem/B can somebody explain the dp solution of this problem as the editorial is not very clear
Name |
---|