module solver
    implicit none
    
contains
    !貪欲法による初期解の生成
    subroutine greedy(D,C,S,T,last,vmax)
        integer(8),intent(in)::D,C(26),S(:,:)
        integer(8),intent(out)::vmax
        integer(8),intent(inout)::T(:),last(:,:)
        integer(8),allocatable::last2(:),V(:),Tans(:),last_best(:,:)
        integer(8) dadd,i,i_calc,j,k,l,tbest,score,vbest
        
        allocate(Tans(D))
        allocate(last_best(26,D))
        allocate(last2(26))
        allocate(V(D))
        
        do dadd=0,26
            T=0
            V=0
            last=0
            last2=0
            !今日の日付+dadd日目のパラメータを使用して満足度を計算する
            do i=1,D
                i_calc=min(i+dadd,D)
                do j=1,26
                    !得点の初期化
                    if(i==1)V(i)=0
                    if(i>1)V(i)=V(i-1)
    
                    !lastの初期化
                    if(i==1)last(:,i)=0
                    if(i>1)last(:,i)=last(:,i-1)
    
                    last(j,i)=i
                    V(i)=V(i)+S(j,i)
                    
                    do k=1,26
                        do l=i,i_calc
                            V(i)=V(i)-C(k)*(l-last(k,i))
                        end do
                    end do
    
                    if(j==1)then
                        vmax=V(i)
                        tbest=j
                    else if(V(i)>=vmax)then
                        vmax=V(i)
                        tbest=j
                    end if
                end do
                if(i==1)last(:,i)=0
                if(i>1)last(:,i)=last(:,i-1)
                T(i)=tbest
                last(tbest,i)=i
            end do
    
            !得点の再計算
            score=0
            last2=0
            do i=1,D
                score=score+S(T(i),i)
                last2(T(i))=i
                do j=1,26
                    score=score-C(j)*(i-last2(j))
                end do
            end do
    
            if(dadd==0.or.score>vbest)then
                vbest=score
                Tans(:)=T(:)
                last_best(:,:)=last(:,:)
            end if
        end do

        vmax=vbest
        T(:)=Tans(:)
        last(:,:)=last_best(:,:)
        return
    end subroutine greedy

    subroutine change_one(D,C,S,T,V,last,vmax)
        integer(8),intent(in)::D,C(26),S(:,:)
        integer(8),intent(inout)::T(D),last(26,D),V(D),vmax
        integer(8)::drand,qrand,contests=26
        integer(8) torigin,i,j,last_sim(26,D),Vorigin(D)

        !乱数の生成
        drand=rnd_int(D)
        qrand=rnd_int(contests)

        last_sim(:,:)=last(:,:)
        Vorigin(:)=V(:)

        !drand日目に行うコンテストをqrandに変更する
        !last_simの書き換え
        torigin=T(drand)

        if(drand==1)then
            last_sim(T(drand),1)=0
            last_sim(qrand,1)=1
        else
            last_sim(T(drand),drand)=last(T(drand),drand-1)
            last_sim(qrand,drand)=drand
        end if

        !日付に対応するコンテストタイプの書き換え
        T(drand)=qrand

        !drand日目の得点の再計算
        if(drand==1)then
            V(drand)=0
        else
            V(drand)=V(drand-1)
        end if
        V(drand)=V(drand)+S(T(drand),drand)
        do i=1,26
            V(drand)=V(drand)-C(i)*(drand-last_sim(i,drand))
        end do

        !drand+1日目以降の得点の再計算
        do i=drand+1,D
            last_sim(:,i)=last_sim(:,i-1)
            V(i)=V(i-1)
            V(i)=V(i)+S(T(i),i)
            last_sim(T(i),i)=i
            do j=1,26
                V(i)=V(i)-C(j)*(i-last_sim(j,i))
            end do
        end do

        if(V(D)>vmax)then
            vmax=V(D)
            last(:,:)=last_sim(:,:)
        else
            V(:)=Vorigin(:)
            T(drand)=torigin
        end if
    end subroutine change_one

    subroutine swap_two(D,C,S,T,V,last,vmax)
        integer(8),intent(in)::D,C(26),S(:,:)
        integer(8),intent(inout)::T(D),last(26,D),V(D),vmax
        integer(8)::swap1,swap2,swap_max,t_swap
        integer(8) i,j,last_sim(26,D),Vorigin(D)

        !swap1とswap2がかぶらないようにかつ差が20以内になるまで乱数を生成
        do
            swap1=rnd_int(D)
            swap2=rnd_int(D)
            if(abs(swap1-swap2)>0.and.abs(swap1-swap2)<=20)exit
        end do

        !swap1<swap2になるようにする
        swap_max=max(swap1,swap2)
        swap1=min(swap1,swap2)
        swap2=swap_max

        !もとの入力を保存
        Vorigin(:)=V(:)
        last_sim(:,:)=last(:,:)

        !T(swap1)をt_swapに格納
        t_swap=T(swap1)

        !swap
        T(swap1)=T(swap2)
        T(swap2)=t_swap

        !swap1から後ろを更新
        do i=swap1,D
            !得点・lastの初期化
            if(i==1)then
                V(i)=0
                last_sim(:,i)=0
            else
                V(i)=V(i-1)
                last_sim(:,i)=last_sim(:,i-1)
            end if
            last_sim(T(i),i)=i
            V(i)=V(i)+S(T(i),i)

            do j=1,26
                V(i)=V(i)-C(j)*(i-last_sim(j,i))
            end do
        end do

        if(V(D)>vmax)then
            vmax=V(D)
            last(:,:)=last_sim(:,:)
        else
            V(:)=Vorigin(:)
            T(swap2)=T(swap1)
            T(swap1)=t_swap
        end if
    end subroutine swap_two

    !整数の乱数生成
    function rnd_int(rnd_max)
        integer(8),intent(in)::rnd_max
        integer(8)::rnd_int
        real::rnd_real
        call random_number(rnd_real)
        rnd_int=mod(int(rnd_real*100000000),rnd_max)+1
        return
    end function
end module solver

program scoring
    use solver
    implicit none
    integer(8)::t1,t2,t_rate,t_max,diff!実行時間の計測関連
    integer(8)::D,C(26),last(26,365),last_sim(26,365),vmax,i,select_mode,modes=2
    integer(8)::steps=0!ベンチマーク用
    integer(8),allocatable::S(:,:),T(:),Tans(:),V(:),Vorigin(:)
    !時間計測開始
    call system_clock(t1)

    !入力
    read*,D,C
    allocate(S(26,D))
    allocate(T(D))
    allocate(Tans(D))
    allocate(V(D))
    allocate(Vorigin(D))
    read*,S
    T=0
    V=0
    last=0
    last_sim=0

    !貪欲法による初期解の生成
    call greedy(D,C,S,T,last,vmax)
    call system_clock(t2,t_rate,t_max)
    diff=t2-t1

    do
        if(diff>1990*t_rate/1000)exit
        steps=steps+1

        !1点変更か2点スワップかランダムに決める
        select_mode=rnd_int(modes)
        if(select_mode==1)call change_one(D,C,S,T,V,last,vmax)
        if(select_mode==2)call swap_two(D,C,S,T,V,last,vmax)

        !時間計測
        call system_clock(t2,t_rate,t_max)
        diff=t2-t1
    end do
    !print*,diff/dble(t_rate),steps

    !答えの出力
    do i=1,D
        print'(i0)',T(i)
    end do
contains

end program scoring

Measured memory_bytes: 3160