Submission #57894314

Source Code Expand

class ST
	def initialize a
		@l = (1<<(a.size-1).bit_length)-1
		@a = [nil]*@l
		@a.concat a
		@a.concat [0]*(@l+1-a.size)
		(@l-1).downto(0){|i|
			@a[i] = @a[i+i+1,2].min
		}
	end

	def [] l,r=l
		return if r<l
		l,r = @l+l,@l+r
		lm,rm = @a[l],@a[r]
		lm,rm,l,r = [@a[l],lm].min,[@a[r],rm].min,l/2,r/2-1 until r<l
		return [lm,rm].min
	end

	def []= i,v
		i += @l
		@a[i] = v
		@a[i] = @a[i+i+1,2].min while 0<=i = (i-1)/2
		return v
	end
end

N,*A = $<.read.split.map(&:to_i)
Sum = A.sum
S = A.cycle(2).inject([0]){|s,a| s<<s[-1]+a*N-Sum }
M = ST.new S
p((1..N).find{|i|
	S[i-1]<=M[i,i+N-2]
}||-1)

Submission Info

Submission Time
Task F - Divide the Cake
User ds14050
Language Ruby (ruby 3.2.2)
Score 500
Code Size 636 Byte
Status AC
Exec Time 596 ms
Memory 78084 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 39
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 02_maximum_00.txt, 02_maximum_01.txt, 02_maximum_02.txt, 02_maximum_03.txt, 02_maximum_04.txt, 03_handmade_00.txt, 03_handmade_01.txt, 03_handmade_02.txt, 03_handmade_03.txt, 03_handmade_04.txt, 03_handmade_05.txt, 03_handmade_06.txt, 03_handmade_07.txt, 03_handmade_08.txt, 03_handmade_09.txt, 03_handmade_10.txt, 03_handmade_11.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 95 ms 17040 KiB
00_sample_01.txt AC 44 ms 17444 KiB
01_random_00.txt AC 355 ms 64544 KiB
01_random_01.txt AC 291 ms 72972 KiB
01_random_02.txt AC 382 ms 72804 KiB
01_random_03.txt AC 350 ms 75016 KiB
01_random_04.txt AC 158 ms 44736 KiB
01_random_05.txt AC 187 ms 51044 KiB
01_random_06.txt AC 483 ms 72680 KiB
01_random_07.txt AC 185 ms 51692 KiB
01_random_08.txt AC 596 ms 77256 KiB
01_random_09.txt AC 419 ms 67984 KiB
01_random_10.txt AC 387 ms 63764 KiB
01_random_11.txt AC 326 ms 72124 KiB
01_random_12.txt AC 543 ms 77844 KiB
01_random_13.txt AC 382 ms 71800 KiB
01_random_14.txt AC 236 ms 62232 KiB
01_random_15.txt AC 404 ms 75428 KiB
01_random_16.txt AC 220 ms 61044 KiB
01_random_17.txt AC 450 ms 73152 KiB
01_random_18.txt AC 208 ms 47200 KiB
01_random_19.txt AC 425 ms 70900 KiB
02_maximum_00.txt AC 407 ms 77856 KiB
02_maximum_01.txt AC 506 ms 77932 KiB
02_maximum_02.txt AC 530 ms 77880 KiB
02_maximum_03.txt AC 372 ms 78020 KiB
02_maximum_04.txt AC 448 ms 77784 KiB
03_handmade_00.txt AC 420 ms 74040 KiB
03_handmade_01.txt AC 433 ms 68600 KiB
03_handmade_02.txt AC 502 ms 77828 KiB
03_handmade_03.txt AC 264 ms 70516 KiB
03_handmade_04.txt AC 277 ms 69340 KiB
03_handmade_05.txt AC 268 ms 78084 KiB
03_handmade_06.txt AC 455 ms 77976 KiB
03_handmade_07.txt AC 269 ms 77896 KiB
03_handmade_08.txt AC 260 ms 75532 KiB
03_handmade_09.txt AC 261 ms 75892 KiB
03_handmade_10.txt AC 304 ms 75604 KiB
03_handmade_11.txt AC 43 ms 17080 KiB