취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28141번 문제인 Easy Interactive Problem이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/28141 

1 이상 N 이하의 정수 \(b_0\)에 대하여 수열 \(b_i = A_{b_{i-1}}\)은 일정한 주기로 반복되는 수열이 됨을 관찰하자.

이 수열의 주기가 1이라면 모든 p에 대하여 \(b_p = b_0\)이 된다.

이 수열의 주기가 1이 아니라 가정하자. 그렇다면  수열의 주기의 배수가 아닌 수 p에 대하여 항상 \(b_p \neq b_0\)이 성립한다. 이제 \(b_p\)부터 수열의 다음 수를 찾는 것을 반복하는 것으로 원래의 순열을 구해낼 수 있게 된다.

위와 같은 아이디어를 이용해 순열을 구하고 문제를 해결하자. 이 때 질문 횟수가 3N/2 이하가 됨은 주기가 1인 사이클의 경우 필요 질문횟수가 1, 그 외의 경우 필요 질문횟수가 k+1(단, k는 사이클의 크기)임을 이용해 간단히 보일 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

int N;
bool sieve[1000000];

queue<int> primeque;

void init() {
	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000000; j += i) sieve[j] = 1;
	}
	for (ll i = 5001; i < 1000000; i += 2) {
		if (sieve[i]) continue;
		primeque.push(i);
	}
}

int ans[1001];
int qnum = -1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	init();

	cin >> N;
	for (int i = 1; i <= N; i++) {
		if (ans[i]) continue;
		while (qnum >= primeque.front()) primeque.pop();
		qnum = primeque.front();

		int ii, iii; queue<int> que;
		cout << '?' << ' ' << i << ' ' << qnum++ << endl;
		cin >> ii; que.push(ii);
		iii = ii;

		if (i != ii) {
			cout << '?' << ' ' << i << ' ' << qnum++ << endl;
			cin >> ii; que.push(ii);

			while (ii != iii) {
				cout << '?' << ' ' << i << ' ' << qnum++ << endl;
				cin >> ii; que.push(ii);
			}

			que.pop();
		}

		int cur = iii;
		while (!que.empty()) {
			ans[cur] = que.front();
			cur = que.front();
			que.pop();
		}
	}

	cout << '!';
	for (int i = 1; i <= N; i++) cout << ' ' << ans[i];
	cout << endl;
}