百駿1015草


リンクテキスト
最初は入力したAを並べ替えるだけで、Pの並べ替えの値をインデックスに変換して、簡単に解きました.
for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i] == arr1[j] && arr[j] != -1) {
				arr[j] = -1;
				p[j] = i;
			}
		}
	}
では、正解があるわけがないでしょう.
もちろん間違っています.
どこに問題があるのか考えてみましたが、コアはA[i]=B[j],j=P[i]でした.
問題の例で言えば.
2 3 1を入力すると、1 2 3にソートされます.A->Bでソートすると、インデックスの変化は0-12から2.01に変わります.なお、Bのみを基準として、1 2 3に対するインデックスは0 1 2である.このインデックス値はP配列と同じです.
よくわかりません.
A[i] = B[P[i]].
ここで並べ替えたAの(値,インデックス)対は(1,2)(2,0)(3,1),Bは(1,0)(2,1)(3,2)である.
値段が1,2,3だと,条件が満たされる.答えはここにある.
Aのインデックスは、P配列の値を決定することができる.
したがって(ソートされたAのインデックス、Bのインデックス(P配列の値)がペアでソートされると、私たちが探しているP配列が現れます.(i=0の場合、A[0]=2,B[?]ga 2になるために?1のはずです.すなわち、P[0]=1である.
(2,0)(0,1)(1,2)対が現れ,対の先頭はPのインデックスであり,後はP配列の値である.
ソート後は(0,1)(1,2)(2,0),P配列の値は120である.
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
	int answer = 0;
	int n;
	int arr[50];

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int arr1[50];
\
	copy(arr, arr + n, arr1); //A
	sort(arr, arr+n); //B

	int p[50];

	vector<pair<int,int>> v;
	for (int i = 0; i < n; i++) {
		pair<int, int> p = make_pair(arr1[i], i);
		v.push_back(p);
	}
	sort(v.begin(), v.end());
		
	vector<pair<int, int>> B;
	for (int i = 0; i < n; i++) {
		pair<int, int> p = make_pair(v[i].second, i);
		B.push_back(p);
	}
	sort(B.begin(), B.end());

	for (int i = 0; i < n; i++) {
		cout << B[i].second << ' ';
	}
}