×

# What's wrong in this code(CHEFEXQ)?

 0 I used Square root decomposition and divided the whole array into buckets where each row in arr represents one bucket. Then I stored the prefix xor's of all the buckets in another 2D array dp. But it's giving wrong answer. Please help! It is always giving right answer for the first query and even update is working fine. But it's giving wrong answer from second query if it is of type 2. #include #include #include using namespace std; int a[100005]; int main() { int n,q; scanf("%d%d",&n,&q); for(int i=0;i< n;i++) scanf("%d",&a[i]); int bsize=(int)floor(sqrt(n)); int nbuck=n/bsize; if(n%bsize!=0) nbuck+=1; int arr[nbuck][bsize]; memset(arr,0,sizeof(arr)); for(int i=0;i< n;i++) { arr[i/bsize][i%bsize]=a[i]; } int dp[nbuck][bsize]; memset(dp,0,sizeof(dp)); int exor; for(int i=0;i< nbuck;i++) { exor=0; for(int j=0;j< bsize;j++) { exor^=arr[i][j]; dp[i][j]=exor; } } int ty,i,x,k,count,buck,end,ans; while(q--) { scanf("%d",&ty); if(ty==1) { scanf("%d%d",&i,&x); i--; arr[i/bsize][i%bsize]=x; exor=0; for(int j=0;j< bsize;j++) { exor^=arr[i/bsize][j]; dp[i/bsize][j]=exor; } } else { scanf("%d%d",&i,&k); i--; ans=0; buck=i/bsize; end=bsize-1; count=0; for(int x=0;x<=buck;x++) { if(x==buck) { end=i%bsize; for(int j=0;j<=end;j++) { ans=ans^dp[x][j]; if(ans==k) count++; } break; } for(int y=0;y<=end;y++) { if(dp[x][y]==(ans^k)) count++; } ans^=dp[x][bsize-1]; } printf("%d\n",count); } } return 0; }  asked 12 Dec '17, 11:50 2★ramini 61●5 accept rate: 8%

 0 Something doesn't work with your bucket size and number of buckets. For example with n = 12 you have floor(sqrt(12)) = 3. So bucket size is 3 and (12 % 3) == 0 so you have only 3 buckets. 3 * 3 = 9 elements are part of a bucket, but you have n = 12 elements. answered 12 Dec '17, 12:31 126●4 accept rate: 23% Thanks bro. Now, I changed the line from (nbuck=bsize) to (nbuck=n/bsize). But even now it's not working. (12 Dec '17, 13:23) ramini2★ It is always giving right answer for the first query and even update is working fine. But it's giving wrong answer from second query if it is of type 2. (12 Dec '17, 13:56) ramini2★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×4
×3

question asked: 12 Dec '17, 11:50

question was seen: 242 times

last updated: 12 Dec '17, 13:56