結果

問題 No.2226 Hello, Forgotten World!
コンテスト
ユーザー ygd.
提出日時 2023-02-24 22:05:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,000 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 81,932 KB
実行使用メモリ 77,700 KB
最終ジャッジ日時 2024-09-13 05:31:32
合計ジャッジ時間 1,631 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline #文字列はダメ
#sys.setrecursionlimit(1000000)
import math
import bisect
#import itertools
#import random
#from heapq import heapify, heappop, heappush
from collections import defaultdict
from collections import deque
import copy #DeepCopy: hoge = [_[:] for _ in hogehoge]
#from functools import lru_cache
#@lru_cache(maxsize=None)
#MOD = pow(10,9) + 7
MOD = 998244353
dx = [1,0,-1,0]
dy = [0,1,0,-1]
#dx8 = [1,1,0,-1,-1,-1,0,1]
#dy8 = [0,1,1,1,0,-1,-1,-1]

base1 = 1007; base2 = 2009
mod1 = 1000000007; mod2 = 1000000009

class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): #S[l:r]indexでいうl文字目からr-1文字目。r-l文字。
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

def get_hash(s,base,mod):
    ns = len(s)
    ret = 0
    v = 0
    for i in range(ns):
        v = (v * base + ord(s[i])) % mod
        ret += v
        ret %= mod
    return ret


def main():
    word = "helloworld"
    ok1 = set([]); ok2 = set([])
    n = len(word)
    for i in range(1<<n):
        temp = ""
        for j in range(n):
            if (i>>j)&1 == 1:
                temp += '?'
            else:
                temp += word[j]
        RH1 = RollingHash(temp,base1,mod1)
        RH2 = RollingHash(temp,base2,mod2)
        ok1.add(RH1.get(0,10))
        ok2.add(RH2.get(0,10))
        if i == 0:
            ori1 = RH1.get(0,10)
            ori2 = RH2.get(0,10)
    
    T = int(input())
    for _ in range(T):
        N = int(input())
        S = input()
        RH1 = RollingHash(S,base1,mod1)
        RH2 = RollingHash(S,base2,mod2)
        ans = []
        # print(RH1.get(0,0+10))
        last = -1; Flag = False
        for i in range(N-9):
            if RH1.get(i,i+10) in ok1 and RH2.get(i,i+10) in ok2:
                last = i
            if RH1.get(i,i+10) == ori1 and RH2.get(i,i+10) == ori2:
                Flag = True
        # print("last",last)
        if last == -1:
            print(-1)
            continue
        if Flag:
            for i in range(N):
                if S[i] == '?':
                    ans.append('a')
                else:
                    ans.append(S[i])
            print("".join(ans))
            continue
        idx = 0
        while idx < N:
            if idx != last:
                if S[idx] == '?':
                    ans.append('a')
                else:
                    ans.append(S[idx])
                idx += 1
            else:
                ans.append("helloworld")
                idx += 10
        # print(ans)
        print("".join(ans))
                    


if __name__ == '__main__':
    main()
0