90分wa#9 求调
查看原帖
90分wa#9 求调
1396485
Ac_two楼主2024/8/21 18:03

如题,感谢大佬伸手援助蒟蒻!

#include<iostream>
#include<algorithm>
using namespace std;
const int N =1000000;
typedef pair<int, int> PII;
PII p[N]; int a[N];
PII w[N], l[N];
bool cmp(PII a, PII b) {
	if (a.first == b.first)return a.second < b.second;
	return a.first > b.first;
}
int main() {
	int n, r, q;
	cin >> n >> r >> q;
	n = 2 * n;
	for (int i = 0; i < n; i++) {
		int temp; cin >> temp;
		p[i] = { temp,i + 1 };
	}
	sort(p, p + n, cmp);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i < r; i++) {
		int wind = 0, lind = 0;
		for (int i = 0; i < n / 2; i++) {
			if (a[p[2 * i].second] > a[p[2 * i + 1].second]) {
				p[2 * i].first+=1;
				w[wind++] = p[2 * i], l[lind++] = p[2 * i + 1];
			}
			else {
				p[2 * i + 1].first+=1;
				w[wind++] = p[2 * i + 1], l[lind++] = p[2 * i];
			}
		}
		int indw = 0, indl = 0, index = 0;
		while (indw <= wind || indl <= lind) {
			if (indl > lind || w[indw].first > l[indl].first) {
				p[index++] = w[indw++];
			}
			else if (indw > wind || w[indw].first < l[indl].first) {
				p[index++] = l[indl++];
			}
			else {
				if (w[indw].second < l[indl].second) {
					p[index++] = w[indw++];
				}
				else {
					p[index++] = l[indl++];
				}
			}
		}
	}
	cout << p[q-1].second << endl;
	return 0;
}
2024/8/21 18:03
加载中...