結果

問題 No.3389 k-Days Later
コンテスト
ユーザー ID 21712
提出日時 2025-12-04 00:36:35
言語 Go
(1.23.4)
結果
RE  
実行時間 -
コード長 1,987 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,510 ms
コンパイル使用メモリ 250,984 KB
実行使用メモリ 8,200 KB
最終ジャッジ日時 2025-12-04 00:37:09
合計ジャッジ時間 29,585 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import . "sort"

func main() {
	rd := bf.NewReader(Stdin)
	wr := bf.NewWriter(Stdout)
	defer wr.Flush()
	var n int
	Fscan(rd, &n)
	ds := make([]int, n)
	sum := make([]int, n+1)
	for i := range ds {
		Fscan(rd, &ds[i])
		sum[i+1] = sum[i]+ds[i]
	}
	var q int
	Fscan(rd, &q)
	for ; q > 0; q-- {
		var y,m,d,k int
		Fscan(rd, &y,&m,&d,&k)
		a,b,c := solve(n, ds, sum, y, m, d, k)
		Fprintln(wr, a, b, c)
	}
}

func solve(n int, ds, sum []int, y, m, d, k int) (int, int, int) {
	y += k / sum[n]
	k = k % sum[n]
	if d+k <= ds[m-1] {
		return y, m, d+k
	}
	r := sum[n]-sum[m]+ds[m-1]-d
	if k <= r {
		k -= ds[m-1]-d+1
		m++
		if m > n {
			m = 1
			y++
		}
		d = 1
	} else {
		k -= r+1
		y++
		m = 1
		d = 1
	}
	if k == 0 {
		return y,m,d
	}
	p := Search(n-m, func(i int) bool {
		return sum[m-1+i]-sum[m-1]>=k+1
	})
	// println(Sprintf("p=%d",p))
	// println(Sprintf("y=%d,m=%d,d=%d,k=%d",y,m,d,k))
	k -= sum[m-1+p-1]-sum[m-1]
	m += p-1
	d += k
	if d > ds[m-1] {
		d -= ds[m-1]
		m++
		if m > n {
			m = 1
			y++
		}
	}
	return y,m,d
}

func bruteforce(n int, ds []int, y, m, d, k int) (int, int, int) {
	for ; k > 0; k-- {
		d++
		if d > ds[m-1] {
			d = 1
			m++
			if m > n {
				m = 1
				y++
			}
		}
	}
	return y,m,d
}

func check() {
	ds := []int{3, 4, 5, 6, 7}
	n := len(ds)
	y := 1
	sum := make([]int, n+1)
	for i, dm := range ds {
		sum[i+1] = sum[i]+dm
	}
	for i, dm := range ds {
		m := i+1
		for d := 1; d <= dm; d++ {
			for k := 1; k < 100; k++ {
				a1,b1,c1 := solve(n, ds, sum, y, m, d, k)
				a2,b2,c2 := bruteforce(n, ds, y, m, d, k)
				if a1 != a2 || b1 != b2 || c1 != c2 {
					println(Sprintf("n=%d",n))
					println(Sprintf("ds=%#v", ds))
					println(Sprintf("sum=%#v", sum))
					println(Sprintf("y=%d,m=%d,d=%d,k=%d",y,m,d,k))
					println(Sprintf("a1=%d,b1=%d,c1=%d",a1,b1,c1))
					println(Sprintf("a2=%d,b2=%d,c2=%d",a2,b2,c2))
					panic("Wrong Answer")
				}
			}
		}
	}
}

func init() {
	check()
}
0