CodingBeast23's blog

Want to know Hint for Question : Google India Summer Internship Program 2021 — Coding Test — 16 August (Ended)
By CodingBeast23, history, 4 years ago, In English

Problem Statement`` ================= : Given a list which initially contains 0, the following queries can be performed:

0 X : Add X to the List

1 X : Replace each element in List With its XOR with X (i.e. Replace A with A^X where is ^ is an XOR operation)

Return a list in increasing order after all queries.

-------- Sample :

-------- Q=5

0 4

0 2

1 4

0 5

1 8

Answer : 8 12 13 14

Let me know the concept in this problem :

Thanks.

Update : Got The Solution : Thanks 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
signed main()
{
    vector<int>v;
    int effect=0;
    int q;
    cin >> q;
    v.push_back(0);
    while(q--)
    {
        int type,x;
        cin >> type >> x;
        if(type==0)
        {
            v.push_back(x);
            v.back()^=effect;
        }
        else
        {
            effect^=x;
        }
    }
    for(int i=0;i<v.size();i++)
    {
        v[i]^=effect;
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
        cout<<v[i]<<' ';

}

Thanks CodeForces Community ... This Was my First Attempt to CF Blogs..

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

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Think about prefix sums

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

    How to solve this with prefix sum?

    Can you explain a little more...

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

      It's not necessarily using prefix sums, but I meant that this concept is helpful in figuring out your solution :P

      → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Process all the queries of type 0 and store the type 1 query in a vector of arrays (say End). Now after getting all the elements, You have some ranges(starting from 1st element). You just have to take Xor all the elements of a particular range with the calculated value.

Lets say we have a variable Xor which is the current value with which we have to take the xor with the i-th element of the given array.

Initially Xor = xor(all X of type 1 query).

Now as you procees forward and leave a range You again take xor of the value proviede for the given range(which ended right before) which will compensate the original Xor taken of all the values provided...

Not clear...?

Have a look at the code and read above strategy again. Hope it is clear now.

#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(0)
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
typedef long long ll;
#define pri(n) printf("%d\n",n)
#define lpri(n) printf("%lld\n",n);
#define rep(i,st,ed) for(int i=st;i<ed;i++)
#define var(n) int n; scn(n)
#define F first
#define S second 
#define pb(n) push_back(n)
#define all(x) (x).begin(),(x).end()
const int N=1e6+6;
const ll M=1e9+7;
const ll inf=1e18+5;

vector<int> End[N];

int main()
{
	ios;
	int T;
	cin>>T;
	while(T--)
	{
		vector<int> v;
		v.push_back(0);
		int q;
		cin>>q;
		int Xor = 0;
		while(q--)
		{
			int type,x;
			cin>>type>>x;
			if(type==0)
			{
				v.push_back(x);
			}
			else
			{
				int sz = v.size();
				End[sz].push_back(x);
				Xor ^= x;
			}
		}
		int sz = v.size();
		for(int i = 0;i<sz;i++)
		{
			v[i] ^= Xor;
			for(auto it : End[i+1])
			{
				Xor ^= it;
			}
		}
		sort(all(v));
		for(auto it : v)
			cout<<it<<' ';
		cout<<"\n";
	}		
}
→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks CodeForces For This Great Community

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it 
n = int(input())
l = [0]
pre = [0]*n 
ind = 0
for i in range(n):
    x,y = [int(m) for m in input().split()]
    if x==0:
        l.append(y)
        ind+=1 
    else:
        pre[ind] = y 
xor = 0

for i in range(len(l)-1,-1,-1):
    xor^=pre[i]
    l[i]^=xor 
print(*sorted(l))
...
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    lmao, this solution is correct. why the downvotes

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Hey just ignore, basically situation is like there are lot of beginner on codeforces almost 99 percentage you could say, so most probably people will upvote you if you already have some upvotes already, or downvote you if downvoted already.
      Else just reach purple+ color and type anything you want, in 95% cases you will get upvotes.

      → Reply