hiroyuk1
@hiroyuk1

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

AtCoder Practice Contest B Interactive Sorting

Q&A

Closed

def ask(s):
  print('?', s[0], s[1], flush = True)
  return input()
def ok(s):
  print('!', s, flush = True)
  exit(0)
n, q = map(int, input().split())
if n == 5 and q == 7:
  if ask("AB") == '<':
    if ask("CD") == '<':
      if ask("AC") == '<':
        if ask("CE") == '<':
          if ask("DE") == '<':
            if ask("BD") == '<':
              ok("ABCDE" if ask("BC") == '<' else "ACBDE")
            else:
              ok("ACDBE" if ask("BE") == '<' else "ACDEB")
          else:
            if ask("BE") == '<':
              ok("ABCED" if ask("BC") == '<' else "ACBED")
            else:
              ok("ACEBD" if ask("BD") == '<' else "ACEDB")
        else:
          if ask("BC") == '<':
            if ask("AE") == '<':
              ok("ABECD" if ask("BE") == '<' else "AEBCD")
            else:
              ok("EABCD")
          else:
            if ask("AE") == '<':
              ok("AECBD" if ask("BD") == '<' else "AECDB")
            else:
              ok("EACBD" if ask("BD") == '<' else "EACDB")
      else:
        if ask("AE") == '<':
          if ask("DE") == '<':
            if ask("BD") == '<':
              ok("CBADE" if ask("BA") == '<' else "CABDE")
            else:
              ok("CADBE" if ask("BE") == '<' else "CADEB")
          else:
            if ask("BE") == '<':
              ok("CBAED" if ask("BA") == '<' else "CABED")
            else:
              ok("CAEBD" if ask("BD") == '<' else "CAEDB")
        else:
          if ask("BA") == '<':
            if ask("CE") == '<':
              ok("CBEAD" if ask("BE") == '<' else "CEBAD")
            else:
              ok("ECBAD")
          else:
            if ask("CE") == '<':
              ok("CEABD" if ask("BD") == '<' else "CEADB")
            else:
              ok("ECABD" if ask("BD") == '<' else "ECADB")
    else:
      if ask("AD") == '<':
        if ask("DE") == '<':
          if ask("CE") == '<':
            if ask("BC") == '<':
              ok("ABDCE" if ask("BD") == '<' else "ADBCE")
            else:
              ok("ADCBE" if ask("BE") == '<' else "ADCEB")
          else:
            if ask("BE") == '<':
              ok("ABDEC" if ask("BD") == '<' else "ADBEC")
            else:
              ok("ADEBC" if ask("BC") == '<' else "ADECB")
        else:
          if ask("BD") == '<':
            if ask("AE") == '<':
              ok("ABEDC" if ask("BE") == '<' else "AEBDC")
            else:
              ok("EABDC")
          else:
            if ask("AE") == '<':
              ok("AEDBC" if ask("BC") == '<' else "AEDCB")
            else:
              ok("EADBC" if ask("BC") == '<' else "EADCB")
      else:
        if ask("AE") == '<':
          if ask("BE") == '<':
            if ask("BC") == '<':
              ok("DABCE" if ask("CE") == '<' else "DABEC")
            else:
              ok("DACBE" if ask("AC") == '<' else "DCABE")
          else:
            if ask("CE") == '<':
              ok("DACEB" if ask("AC") == '<' else "DCAEB")
            else:
              ok("DAEBC" if ask("BC") == '<' else "DAECB")
        else:
          if ask("AC") == '<':
            if ask("DE") == '<':
              ok("DEABC" if ask("BC") == '<' else "DEACB")
          else:
            if ask("DE") == '<':
              ok("DCEAB" if ask("CE") == '<' else "DECAB")
            else:
              ok("EDCAB")
  else:
    if ask("CD") == '<':
      if ask("BC") == '<':
        if ask("CE") == '<':
          if ask("DE") == '<':
            if ask("AD") == '<':
              ok("BACDE" if ask("AC") == '<' else "BCADE")
            else:
              ok("BCDAE" if ask("AE") == '<' else "BCDEA")
          else:
            if ask("AE") == '<':
              ok("BACED" if ask("AC") == '<' else "BCAED")
            else:
              ok("BCEAD" if ask("AD") == '<' else "BCEDA")
        else:
          if ask("AC") == '<':
            if ask("BE") == '<':
              ok("BAECD" if ask("AE") == '<' else "BEACD")
            else:
              ok("EBACD")
          else:
            if ask("BE") == '<':
              ok("BECAD" if ask("AD") == '<' else "BECDA")
            else:
              ok("EBCAD" if ask("AD") == '<' else "EBCDA")
      else:
        if ask("BE") == '<':
          if ask("DE") == '<':
            if ask("AD") == '<':
              ok("CABDE" if ask("AB") == '<' else "CBADE")
            else:
              ok("CBDAE" if ask("AE") == '<' else "CBDEA")
          else:
            if ask("AE") == '<':
              ok("CABED" if ask("AB") == '<' else "CBAED")
            else:
              ok("CBEAD" if ask("AD") == '<' else "CBEDA")
        else:
          if ask("AB") == '<':
            if ask("CE") == '<':
              ok("CAEBD" if ask("AE") == '<' else "CEABD")
            else:
              ok("ECABD")
          else:
            if ask("CE") == '<':
              ok("CEBAD" if ask("AD") == '<' else "CEBDA")
            else:
              ok("ECBAD" if ask("AD") == '<' else "ECBDA")
    else:
      if ask("BD") == '<':
        if ask("DE") == '<':
          if ask("CE") == '<':
            if ask("AC") == '<':
              ok("BADCE" if ask("AD") == '<' else "BDACE")
            else:
              ok("BDCAE" if ask("AE") == '<' else "BDCEA")
          else:
            if ask("AE") == '<':
              ok("BADEC" if ask("AD") == '<' else "BDAEC")
            else:
              ok("BDEAC" if ask("AC") == '<' else "BDECA")
        else:
          if ask("AD") == '<':
            if ask("BE") == '<':
              ok("BAEDC" if ask("AE") == '<' else "BEADC")
            else:
              ok("EBADC")
          else:
            if ask("BE") == '<':
              ok("BEDAC" if ask("AC") == '<' else "BEDCA")
            else:
              ok("EBDAC" if ask("AC") == '<' else "EBDCA")
      else:
        if ask("BE") == '<':
          if ask("AE") == '<':
            if ask("AC") == '<':
              ok("DBACE" if ask("CE") == '<' else "DBAEC")
            else:
              ok("DBCAE" if ask("BC") == '<' else "DCBAE")
          else:
            if ask("CE") == '<':
              ok("DBCEA" if ask("BC") == '<' else "DCBEA")
            else:
              ok("DBEAC" if ask("AC") == '<' else "DBECA")
        else:
          if ask("BC") == '<':
            if ask("DE") == '<':
              ok("DEBAC" if ask("AC") == '<' else "DEBCA")
          else:
            if ask("DE") == '<':
              ok("DCEBA" if ask("CE") == '<' else "DECBA")
            else:
              ok("EDCBA")

AtCoder practice contest B Interactive Sortingの3つ目の部分点で5ケースだけ落ちる。120通り全部調べてくれるツールみたいなやつってありますか?または直接どこが間違ってますか?

0

2Answer

120パターン中、下記の14パターンで正しくない結果となりました。

# テストパターン
61 CDABE
62 CDAEB
63 CDBAE
64 CDBEA
65 CDEAB
66 CDEBA
71 CEDAB
72 CEDBA
113 ECDAB
114 ECDBA
115 EDABC
116 EDACB
117 EDBAC
118 EDBCA

作成したジャッジプログラムのコードも載せておきます。引数で1〜120を指定します。

judge.py
import sys
import itertools
questions = []
for q in itertools.permutations(["A", "B", "C", "D", "E"]):
    questions.append(q)
argv = sys.argv
argc = len(argv)
qno = 1 if argc < 2 else int(argv[1])
question = questions[qno - 1]
print(qno, ''.join(question), end =' ', file=sys.stderr)
N, Q = 5, 7
print(N, Q, flush=True)
while True:
    try:
        line = input()
    except EOFError:
        print("WA EOF", file=sys.stderr)
        break
    line = line.split()
    c = line[0]
    if c == "?":
        if Q > 0:
            Q -= 1
            try:
                indexa = question.index(line[1])
                indexb = question.index(line[2])
            except ValueError:
                print("WA index", file=sys.stderr)
                break                    
            print("<" if indexa < indexb else ">", flush=True)
        else:
            print("WA Q", file=sys.stderr)
            break
    elif c == "!":
        wj = "AC" if line[1] == ''.join(question) else "WA"
        print(wj, line[1], file=sys.stderr)
        break
    else:
        print("WA ?!", file=sys.stderr)
        break

FIFOでつないで使います。

$ mkfifo fifo #1回だけ作る
$ python judge.py 114 <fifo | python a.py >fifo
114 ECDBA WA ECBDA
$ python judge.py 120 <fifo | python a.py >fifo
120 EDCBA AC EDCBA
0Like

Comments

  1. @hiroyuk1

    Questioner

    ありがとうございます。

  2. @hiroyuk1

    Questioner

    通りました。

  3. 通りました。

    おめでとうございます。
    他の方の参考になると思うので、ACしたコードを提示してもらえるとありがたいと思います。
    また、当Q&Aをクローズしてください。

ACコード

def ask(s):
  print('?', s[0], s[1], flush = True)
  return input() == '<'
def ok(s):
  print('!', s, flush = True)
  exit(0)
n, q = map(int, input().split())
if n == 26:
  s = ['A']
  for i in "BCDEFGHIJKLMNOPQRSTUVWXYZ":
    l = 0
    r = len(s)
    while l < r:
      m = (l + r) // 2
      if ask(s[m] + i):
        l = m + 1
      else:
        r = m
    s.insert(l, i)
  ok(''.join(s))
else:
  if ask("AB"):
    if ask("CD"):
      if ask("AC"):
        if ask("CE"):
          if ask("DE"):
            if ask("BD"): ok("ABCDE" if ask("BC") else "ACBDE")
            else:         ok("ACDBE" if ask("BE") else "ACDEB")
          else:
            if ask("BE"): ok("ABCED" if ask("BC") else "ACBED")
            else:         ok("ACEBD" if ask("BD") else "ACEDB")
        else:
          if ask("AE"):
            if ask("BC"): ok("ABECD" if ask("BE") else "AEBCD")
            else:         ok("AECBD" if ask("BD") else "AECDB")
          else:
            if ask("BD"): ok("EABCD" if ask("BC") else "EACBD")
            else:         ok("EACDB")
      else:
        if ask("AE"):
          if ask("BE"):
            if ask("BD"): ok("CABDE" if ask("DE") else "CABED")
            else:         ok("CADBE" if ask("AD") else "CDABE")
          else:
            if ask("DE"): ok("CADEB" if ask("AD") else "CDAEB")
            else:         ok("CAEBD" if ask("BD") else "CAEDB")
        else:
          if ask("CE"):
            if ask("AD"): ok("CEABD" if ask("BD") else "CEADB")
            else:         ok("CDEAB" if ask("DE") else "CEDAB")
          else:
            if ask("AD"): ok("ECABD" if ask("BD") else "ECADB")
            else:         ok("ECDAB")
    else:
      if ask("AD"):
        if ask("DE"):
          if ask("CE"):
            if ask("BC"): ok("ABDCE" if ask("BD") else "ADBCE")
            else:         ok("ADCBE" if ask("BE") else "ADCEB")
          else:
            if ask("BE"): ok("ABDEC" if ask("BD") else "ADBEC")
            else:         ok("ADEBC" if ask("BC") else "ADECB")
        else:
          if ask("AE"):
            if ask("BD"): ok("ABEDC" if ask("BE") else "AEBDC")
            else:         ok("AEDBC" if ask("BC") else "AEDCB")
          else:
            if ask("BC"): ok("EABDC" if ask("BD") else "EADBC")
            else:         ok("EADCB")
      else:
        if ask("AE"):
          if ask("BE"):
            if ask("BC"): ok("DABCE" if ask("CE") else "DABEC")
            else:         ok("DACBE" if ask("AC") else "DCABE")
          else:
            if ask("CE"): ok("DACEB" if ask("AC") else "DCAEB")
            else:         ok("DAEBC" if ask("BC") else "DAECB")
        else:
          if ask("DE"):
            if ask("AC"): ok("DEABC" if ask("BC") else "DEACB")
            else:         ok("DCEAB" if ask("CE") else "DECAB")
          else:
            if ask("AC"): ok("EDABC" if ask("BC") else "EDACB")
            else:         ok("EDCAB")
  else:
    if ask("CD"):
      if ask("BC"):
        if ask("CE"):
          if ask("DE"):
            if ask("AD"): ok("BACDE" if ask("AC") else "BCADE")
            else:         ok("BCDAE" if ask("AE") else "BCDEA")
          else:
            if ask("AE"): ok("BACED" if ask("AC") else "BCAED")
            else:         ok("BCEAD" if ask("AD") else "BCEDA")
        else:
          if ask("BE"):
            if ask("AC"): ok("BAECD" if ask("AE") else "BEACD")
            else:         ok("BECAD" if ask("AD") else "BECDA")
          else:
            if ask("AD"): ok("EBACD" if ask("AC") else "EBCAD")
            else:         ok("EBCDA")
      else:
        if ask("BE"):
          if ask("AE"):
            if ask("AD"): ok("CBADE" if ask("DE") else "CBAED")
            else:         ok("CBDAE" if ask("BD") else "CDBAE")
          else:
            if ask("DE"): ok("CBDEA" if ask("BD") else "CDBEA")
            else:         ok("CBEAD" if ask("AD") else "CBEDA")
        else:
          if ask("CE"):
            if ask("BD"): ok("CEBAD" if ask("AD") else "CEBDA")
            else:         ok("CDEBA" if ask("DE") else "CEDBA")
          else:
            if ask("BD"): ok("ECBAD" if ask("AD") else "ECBDA")
            else:         ok("ECDBA")
    else:
      if ask("BD"):
        if ask("DE"):
          if ask("CE"):
            if ask("AC"): ok("BADCE" if ask("AD") else "BDACE")
            else:         ok("BDCAE" if ask("AE") else "BDCEA")
          else:
            if ask("AE"): ok("BADEC" if ask("AD") else "BDAEC")
            else:         ok("BDEAC" if ask("AC") else "BDECA")
        else:
          if ask("BE"):
            if ask("AD"): ok("BAEDC" if ask("AE") else "BEADC")
            else:         ok("BEDAC" if ask("AC") else "BEDCA")
          else:
            if ask("AC"): ok("EBADC" if ask("AD") else "EBDAC")
            else:         ok("EBDCA")
      else:
        if ask("BE"):
          if ask("AE"):
            if ask("AC"): ok("DBACE" if ask("CE") else "DBAEC")
            else:         ok("DBCAE" if ask("BC") else "DCBAE")
          else:
            if ask("CE"): ok("DBCEA" if ask("BC") else "DCBEA")
            else:         ok("DBEAC" if ask("AC") else "DBECA")
        else:
          if ask("DE"):
            if ask("BC"): ok("DEBAC" if ask("AC") else "DEBCA")
            else:         ok("DCEBA" if ask("CE") else "DECBA")
          else:
            if ask("BC"): ok("EDBAC" if ask("AC") else "EDBCA")
            else:         ok("EDCBA")
0Like

Your answer might help someone💌