As an author, you are following me.

Too bad testers can't Register to participate

As a student,I participated in almost all recent rounds……

what __baozii__ thinks:

Why I failed to register the round by clicking the Register button?

except the problems that need you to know the mind of the creator of the problem

The Register button is not working, it directs to a profile.

As a participant, I wanna say, ru1_er (not rui_er at all!) is a very lovely girl!!!

How dare you call yourself a "tester" and CURSE others like that?

I hope you become candidate master in this contest

good luck! I wanna finally rich cyan

can be 0 also or 3 also

Well, if you don't care about the rating, you can always participate in div3

I hope you get -7

The only goal i achieved in my life:

Ciallo～ (∠・ω< )⌒★

Congratulations maga!

Congrats on cheating your way to CM. I hope you will be banned at some point.

Believe in yourself; you can do it.

please register and do your best in the contest ...

and then don't look at scoreboard LOL. but I hope it goes well for you.

anyway it will not be 1.

I found both A and B more puzzling than C as I was able to see the DP for C quite quickly somehow

The idea is: If you have a cycle with even length, all vertices have to have the same value, if you have a cycle with odd length, all vertices have to have value 0. Now you can just calculate all 2-edge connected components (calculate all bridges) and check if each component is bipartite or not.

Look at any cycle. For any two vertices $$$U$$$ and $$$V$$$ on it, by checking paths from $$$U$$$ to $$$V$$$, you get that XOR of all vertices on the cycle except for $$$U$$$ and $$$V$$$ is $$$0$$$, which implies that the XOR of $$$U$$$ and $$$V$$$ is the XOR of the whole cycle, which further implies that all vertices on the same cycle have to have the same value. Additionaly, if the cycle is odd, that value has to be $$$0$$$ (there is a path containing all cycle vertices). It can be verified that these conditions are sufficient.

Now, note that the fact that cycles have all values equal implies that every connected bridgeless subgraph has all values equal. Therefore, you can just find all bridges in the graph, see how it decomposes, and make sure that every component like this has all values equal, and if it contains an odd cycle, that value is $$$0$$$. Now, either you have no condition on the value itself ($$$V$$$ options), exactly one condition (one distinct weight or an odd cycle), so one option, or two contradictory conditions and it's impossible.

When $$$W = 99999$$$ your second query may not function as your wish. $$$49999, 1, 49999$$$ will be displayed in one line.

Look into Bi-connected components, once u observe that bipartite bccs have to have the same value, and non-bipartite bccs should have 0, you have to condense the graph into a tree like structure and then multiply (You also have to merge the bccs which have the same node, as all of the bccs will have to obey the 0 or same value property). Probably the longest solution i've written.

Bridge, though I was not able to solve it during contest.

div2c is not a simple dp as n = 10^5, it is classic fenwick tree . like it was asked before if I am not wrong in cf

Use n=12900 and a[1]=110.

The main idea use $$$1$$$ in the first query.

TC4 was probably $$$75000 \lt W \lt 10^5$$$, because my submission failed on such testcases.

My idea was to have the first query be $$$1,1,1,\dots$$$, $$$10^5$$$ times, and with that info and some NT I would get the lower and upper bound for $$$W$$$: $$$\lceil\frac{10^5}L\rceil\le W\le\lfloor\frac{N-1}{L-1}\rfloor$$$.

Then for each possible integer $$$W$$$ I would insert two words of length $$$\lfloor\frac W2\rfloor$$$ and $$$\lceil\frac W2\rceil$$$, expecting to have two words per line until the true $$$W$$$, and then (with the true $$$W$$$) to have one word per line.

But it seems to fail above $$$75000$$$ because at that point $$$3$$$ words of size $$$25000$$$ can fit on a line. I tried to fix that but I didn't have sufficient time until the end of the contest.

I figured out that we will use bridge here. But was not able to implement correctly during contest. Now, I have done some changes, and waiting to submit & see whether it will get accepted or not.

can u elaborate? i had almost finished this exact problem but today's contest started so i left it xd

1. Do 2 queries moving up by 1e9.
2. Do 2 queries moving right by 1e9.
3. Get the distance for (X + 2e9, Y + 2e9). This distance will be from the anchor point (xi,yi) which is closest to (1e9, 1e9).
4. equate this distance, you will get (X+Y) value from the equation
5. Now, do 6 queries moving down by 1e9
6. New point is (X + 2e9, Y — 4e9). This distance will be from the anchor point (xj, yj) closest to (1e9, -1e9).
7. Do the equation, you will get X-Y.
8. Calculate X and Y.

First query $$$n = 10^5$$$, $$$a_i = 1$$$, lets call the response $$$q_1$$$.

Then check how many values of $$$W$$$ would have satisfies $$$\lceil \frac{10^5}{W} \rceil = q_1$$$. You will get a range of possible values $$$[l, r]$$$.

Observe that this range will always satisfy $$$r \leq 2 \cdot l$$$ and $$$(r - l + 1)$$$ is at most $$$5 \cdot 10^4$$$ (the range [50000, 99999] for $$$q_1 = 2$$$).

So we can just query the following values — $$$l, l, 1, l, 2, l, 3, \cdots, l, r - l$$$. Notice that the corresponding values $$$l, x$$$ will be on the same line if $$$l + x \leq W$$$ or on separate lines if not. So if the response is $$$q_2$$$, the answer is just $$$r - (q_2 - l)$$$.

Just increase $$$a_i$$$ to $$$125$$$ and make sure to query $$$1.5\times 10^4$$$ ones if you get a $$$0$$$. That works.