https://www.codechef.com/FEB18/problems/PERMPAL
長さNの文字列Sがある。
これについて、要素数Nの順列Pを作る。
「P[i] := P[i]文字目をi番目に持ってくる」という操作をすると、結果が回文となる順列Pを求めよ。
もし、回文を作れないなら"-1"
解法
https://www.codechef.com/viewsolution/17299649
まず、「文字毎に文字数を数えた時に文字数が奇数である文字が1個以下なら回文が作れる」という性質を思い出そう。
なので、「cnt[c] := 文字cが何個あるか」を作って、奇数個が2個以上なら"-1"を返そう。
あとは、回文を作るのだが、スワップする前にbufを作ろう。
buf[c] := 文字列Sで文字cがある添字のキュー
これを作ったら、cntを使いながら回文を構築する。
回文から順列を作るにはbufで何番目かを順番に使っていけば求まる。
string S; //--------------------------------------------------------------------------------------------------- void solve() { cin >> S; int n = S.length(); map<char, int> cnt; fore(c, S) cnt[c]++; int odd = 0; char oddc; fore(p, cnt) if (p.second % 2 == 1) odd++, oddc = p.first; if (1 < odd) { printf("-1\n"); return; } map<char, queue<int>> buf; rep(i, 0, n) buf[S[i]].push(i + 1); int idx = 0; fore(p, cnt) { if (p.second % 2 == 1) { S[n / 2] = p.first; p.second--; } while (p.second) { S[idx] = S[n - 1 - idx] = p.first; p.second -= 2; idx++; } } rep(i, 0, n) { if (i) printf(" "); int ans = buf[S[i]].front(); buf[S[i]].pop(); printf("%d", ans); } printf("\n"); } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) solve(); }