Submission #915339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915339	2024-01-23T17:53:03 Z	bobbilyking	IOI Fever (JOI21_fever)	Java 11	Compilation error	0 ms	0 KB

fever

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. 

Compilation message

fever.java:1: error: class, interface, or enum expected
subtask 1:
^
fever.java:23: error: class, interface, or enum expected
Things on the "diagonal" must be moved directly to axis; no way to play catchup. 
                                                         ^
fever.java:25: error: unclosed character literal
Okay, so let's fix direction as up.
            ^
fever.java:33: error: unclosed character literal
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). 
                          ^
fever.java:37: error: unclosed character literal
So it's like a "graph search" almost: We fix direction of initial dude, then keep on shooting out rays in the correct direction. 
     ^
fever.java:41: error: unclosed character literal
(No equals when all coordinates are distinct, but I suspect it's just strict equals).
                                                              ^
fever.java:57: error: unclosed character literal
Basically, it's never worth it to pick a movement vector "away" from the origin. 
             ^
fever.java:62: error: unclosed character literal
		- When coordinates are not distinct (on origin axis), there's only one valid direction: move towards origin. 
		                                                           ^
8 errors