与其他离线做法思想一致,难点在于stl的细节问题
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <string.h>
#include <algorithm>
#include <climits>
#include <stdlib.h>
#include <set>
#include <list>
#include <assert.h>
using namespace std;
const int N = 100010;
list<int>::iterator bok[N];
int res[N / 2];
const int LOW = 0, EQUAL = 1, HIGH = 2;
int query(const list<int>& a, const list<int>::iterator& cur, const list<int>::iterator& aim) {
if (aim == cur)return EQUAL;
if (*aim > *cur)return HIGH;
if (*aim < *cur)return LOW;
for (auto it = cur; it != a.end(); ++it) {
if (*it != *cur)break;
if (aim == it)return HIGH;
}
return LOW;
}
int main() {
int t;
cin >> t;
while (t--) {
int num;
cin >> num;
int n;
cin >> n;
std::cout << num << ' ' << n / 2 + 1 << endl;
list<int> a;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a.push_front(x);
bok[i] = a.begin();
}
a.sort();
list<int>::iterator ans;
list<int>::iterator l = a.begin(), r = a.end();
--r;
/*for (auto it = a.begin(); it != a.end(); ++it)std::cout << *it << ' ';
std::cout << endl;*/
int lcnt = 0, rcnt = 0;
while (1) {
if (l == r) { ans = l; break; }
else {
--r; ++rcnt;
if (l == r) { ans = l; break; }
else { ++l; ++lcnt; }
}
}
//std::cout << *ans << endl;
for (int i = n; i >= 2; i--) {
//printf("%d轮:%d\n", i, *ans);
// 记录结果
if (i & 1)res[i / 2] = *ans;
// 尝试删除该节点,同时保证ans的正确性
/*if (ans == bok[i]) {
if (i & 1) --ans;
else ++ans;
}
else {
if (i & 1) {
if (*ans < *bok[i])--ans;
}
else {
if (*ans > *bok[i])++ans;
}
}*/
int info = query(a, ans, bok[i]);
if (info == LOW) {
if (i & 1);
else ++ans;
}
else if (info == HIGH) {
if (i & 1)--ans;
else;
}
else if(info == EQUAL){
if (i & 1)--ans;
else ++ans;
}
a.erase(bok[i]);
}
printf("%d ", *ans);
for (int i = 1; i <= n / 2; i++) {
if (i % 10 == 0)std::cout << endl;
printf("%d ", res[i]);
}
puts("");
}
}