시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB84450.000%

문제

Это интерактивная задача.

При проведении раскопок на территории Республики Татарстан были обнаружены останки неизвестного древнего животного, обитавшего в окрестностях современной Казани миллионы лет назад. Как и у всех живых организмов, молекула его ДНК представляет собой последовательность из n нуклеотидов, однако число встречающихся в ней различных нуклеотидов может отличаться от современных организмов.

Для изучения находки был создан специальный прибор, который может просканировать последовательный участок нуклеотидов в ДНК и вычислить, сколько различных видов нуклеотидов содержится на нём. К сожалению, молекула ДНК может выдержать не более q операций сканирования, после чего разрушается.

Исследователи хотят с помощью этого прибора найти k — количество различных нуклеотидов в ДНК, и определить позиции, в которых в ДНК находятся одинаковые нуклеотиды. Ученые хотят закодировать последовательность нуклеотидов в молекуле последовательностью целых положительных чисел a1, a2, . . . , an (1 ⩽ ai ⩽ k), таких что одинаковые числа кодируют одинаковые нуклеотиды, а различные числа — различные нуклеотиды.

Требуется написать программу, которая, взаимодействуя с программой жюри, определит количество различных нуклеотидов в последовательности, а также числовую последовательность, кодирующую последовательность нуклеотидов в молекуле ДНК.

프로토콜

При запуске решения на вход подается целое число n — длина молекулы ДНК (1 ⩽ n ⩽ 3 000).

Для каждого теста зафиксированы числа k — количество различных нуклеотидов (1 ⩽ k ⩽ n) и q — максимальное количество запросов. Гарантируется, что q запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе участника, но ограничения на эти числа в различных подзадачах приведены в таблице системы оценивания. Если программа участника делает более q запросов программе жюри, на этом тесте она получает в качестве результата тестирования «Неверный ответ».

Чтобы сделать запрос, следует вывести строку «? i j», где i и j — целые положительные числа, номера первого и последнего нуклеотида непрерывного участка молекулы ДНК, для которого требуется узнать число различных нуклеотидов в нём (1 ⩽ i ⩽ j ⩽ n).

В ответ на каждый запрос программа получает целое число p — количество различных нуклеотидов в фрагменте ДНК, указанном в запросе.

Если программа определила ответ на задачу, то она должна вывести три строки. Первая строка должна содержать слово «Ready!». Вторая строка должна содержать целое число k — количество различных нуклеотидов в молекуле. Третья строка должна содержать последовательность n целых чисел, разделенных пробелами: a1, a2, . . . , an — коды нуклеотидов (1 ⩽ ai ⩽ k). Если подходящих последовательностей несколько, то допускается вывести любую из них.

После этого программа должна завершиться.

서브태스크

번호배점제한
120

1 ⩽ n ⩽ 300, 1 ⩽ k ⩽ 2, q = 72 000

225

1 ⩽ n ⩽ 300, 1 ⩽ k ⩽ n, q = 72 000

325

1 ⩽ n ⩽ 3 000, 1 ⩽ k ⩽ 10, q = 72 000

415

1 ⩽ n ⩽ 3 000, 1 ⩽ k ⩽ n, q = 72 000

515

1 ⩽ n ⩽ 3 000, 1 ⩽ k ⩽ n, q = 36 000

예제 입력 1

2
2

예제 출력 1

? 1 2
Ready!
2
1 2

예제 입력 2

3
1
2

예제 출력 2

? 1 2
? 1 3
Ready!
2
1 1 2

힌트

В первом примере n = 2, за один запрос можно определить, равны ли первый и второй нуклеотид друг другу.

В втором примере n = 3, результат первого запроса показывает, что первые два нуклеотида одинаковые, результат второго запроса позволяет сделать вывод о том, что третий нуклеотид от них отличается. В этом случае допустимы два варианта ответа: 1 1 2 и 2 2 1.

В точности соблюдайте формат выходных данных. После каждого вывода обязательно выводите один перевод строки и сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

채점 및 기타 정보

  • 예제는 채점하지 않는다.