| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 915339 | bobbilyking | IOI Fever (JOI21_fever) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
subtask 1:
4^7 brute force, with sweepline ish events
subtask 2:
Based on observation 1, each vector only has 2^15 possibilities, so run brute force yet again.
Subtask 3:
It says that everybody is in the upper right quadrant.
Okay, well everybdoy can only move down and to the left.
We only get infected when we cross the line.
Therefore, we pick a direction for origin, and then just greedily make everybdoy face that direction. O(n).
(Also notice that it only works for things on the main diagonal...)
Subtask 4:
Things on the "diagonal" must be moved directly to axis; no way to play catchup.
Okay, so let's fix direction as up.
Move all points on the two side diagonals towards middle.
Now, we have a ray shooting out, that also shoots out to some direction at certain timesteps.
Now, relative to those guy's starting rays, any point within the "diagonal square" or whatever will get hit (but at a distance > its current marked time).
Remember, the direction is fixed so this works.
So it's like a "graph search" almost: We fix direction of initial dude, then keep on shooting out rays in the correct direction.
The only condition is that (distance (>=?) currentyl marked time), then we mark it with distance (i.e. the distances are nondecreasing).
(No equals when all coordinates are distinct, but I suspect it's just strict equals).
How to simulate fast?
==================================
Impleemtnation si still a bit cancer at this stpe, make some more observations.
===============================================================
Observation 1: (distinct coordinates only)
Divide up the board into quadrants relative to origin (point 1).
Basically, it's never worth it to pick a movement vector "away" from the origin.
Since I can always outrun the origin.
Observation 1.5:
- When coordinates are not distinct (on origin axis), there's only one valid direction: move towards origin.
===============================================================
Impl detail:
- To do all 4 directions, first center at origin then do rotation (-y, x) or some shit.