# 11593: 【原1593】Mouse

### 题目描述

author: Blacko 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1593

## Description

2N只编号从02N的野生Mouse进行R轮比赛. 每轮比赛开始前, 以及所有比赛结束后, 都会按照每只野生Mice的分数从高到低对选手进行一次排名.约定编号较小的选手排名靠前.

Mouse之间只进行单纯的力量较量, 每场比赛胜者得 2 分，负者得 0 分, 平手各得 1 分. 也就是说除了首轮以外, 其它轮比赛的安排均不能事先确定, 而是要取决于野生Mouse在之前比赛中的表现.

## Sample Input

10 10
0 10 49 24 7 1 64 8 52 81 4 9 40 17 52 17 40 0 97 77
0 1 0 1 1 1 0 2 1 0 0 2 1 1 2 0 1 1 1 0


## Sample Output

19 10 20 7 15 9 13 17 3 4 14 12 8 2 16 5 6 18 11 1


## Limits

10%的数据 $$N \leq 10, R \leq 10, P \leq 10^8, S \leq 10^8$$

30%的数据 $$N \leq 10^2, R \leq 60, P \leq 10^8, S \leq 10^8$$

70%的数据 $$N \leq 10^4, R \leq 60, P \leq 10^8, S \leq 10^8$$

100%的数据 $$N \leq 10^5, R \leq 60, P \leq 10^8, S \leq 10^8$$

## BugenZhao's solution

//
// Created by BugenZhao on 2019/3/17.
//
// 排序

#include <iostream>
#include <algorithm>

using namespace std;

using ll=long long;

int currentID = 0;

class Mouse {
public:
int id;
int power = 0;
int score = 0;

bool operator<(const Mouse &rhs) const {
if (score > rhs.score)
return true;
if (rhs.score > score)
return false;
return id < rhs.id;
}

Mouse() { id = ++currentID; }
};

int main() {
int N, R;
cin >> N >> R;
auto mice = new Mouse[2 * N]{};
int tmp;
for (int i = 0; i < 2 * N; ++i) {
scanf("%d", &mice[i].score);
}
for (int i = 0; i < 2 * N; ++i) {
scanf("%d", &mice[i].power);
}
while (R--) {
sort(mice, mice + 2 * N);
for (int i = 0; i < N; ++i) {
Mouse *a = mice + 2 * i;
Mouse *b = mice + 2 * i + 1;
if (a->power < b->power) {
b->score += 2;
} else if (a->power > b->power) {
a->score += 2;
} else {
a->score += 1;
b->score += 1;
}
}
}
sort(mice, mice + 2 * N);
for (int j = 0; j < 2 * N; ++j) {
printf("%d ", mice[j].id);
}
return 0;
}


## FineArtz's solution

/* Mouse */
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

class Mouse{
public:
Mouse() = default;
Mouse(int x, int y, int z) : id(x), score(y), abi(z) {}
int id = 0, score = 0, abi = 0;
bool operator <(const Mouse &m){
return (score > m.score || score == m.score && id < m.id);
}
};

int n, r;
Mouse win[200005], draw[200005], lose[200005], rk[200005];

void merge(int ww, int dd, int ll){
int w = 1, d = 1, l = 1, p = 0;
while (p <= 2 * n){
if (win[w] < draw[d] && win[w] < lose[l]){
rk[++p] = win[w++];
}
else if (draw[d] < win[w] && draw[d] < lose[l]){
rk[++p] = draw[d++];
}
else if (lose[l] < win[w] && lose[l] < draw[d]){
rk[++p] = lose[l++];
}
else break;
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> r;
for (int i = 1; i <= 2 * n; ++i){
cin >> rk[i].score;
rk[i].id = i;
}
for (int i = 1; i <= 2 * n; ++i)
cin >> rk[i].abi;
sort(rk + 1, rk + 2 * n + 1);
int w, d, l;
for (int round = 1; round <= r; ++round){
w = 0, d = 0, l = 0;
for (int race = 1; race <= n; ++race){
if (rk[race * 2 - 1].abi > rk[race * 2].abi){
rk[race * 2 - 1].score += 2;
win[++w] = rk[race * 2 - 1];
lose[++l] = rk[race * 2];
}
else if (rk[race * 2 - 1].abi == rk[race * 2].abi){
++rk[race * 2 - 1].score;
++rk[race * 2].score;
draw[++d] = rk[race * 2 - 1];
draw[++d] = rk[race * 2];
}
else{
rk[race * 2].score += 2;
win[++w] = rk[race * 2];
lose[++l] = rk[race * 2 - 1];
}
}
win[w + 1] = Mouse(0, -1, 0);
draw[d + 1] = Mouse(0, -1, 0);
lose[l + 1] = Mouse(0, -1, 0);
merge(w, d, l);
}
for (int i = 1; i <= 2 * n; ++i)
cout << rk[i].id << " ";
cout << '\n';
return 0;
}


## ligongzzz's solution

#include "cstdio"
#include "iostream"
#include "cmath"
using namespace std;

constexpr int mod = (int)(1e8);

struct mouse_type {
long long val = 0, strength = 0;
} mouse[200009];

bool cmp(const int& a, const int& b) {
return mouse[a].val > mouse[b].val || (mouse[a].val == mouse[b].val && a < b);
}

int paiwei[200009] = { 0 };

template <class T, class T_val = decltype(*declval<T>()),
class Compare = bool (*)(T_val, T_val)>
void quick_sort(T start, T end,
Compare cmp = [](T_val a, T_val b) {return a < b; }) {
if (start == end)
return;
auto i = start, j = end;
--j;
if (i == j)
return;
//交换
auto key = *start;
for (bool status = true; i != j;) {
if (status) {
if (cmp(*j, key)) {
*i = *j;
++i;
status = false;
}
else
--j;
}
else {
if (cmp(key, *i)) {
*j = *i;
--j;
status = true;
}
else
++i;
}
}
*i = key;
//递归
quick_sort(start, ++i, cmp);
quick_sort(i, end, cmp);
}

void arrange(int pos) {
auto temp = paiwei[pos];
auto p = pos - 1;
for (; p >= 0; --p) {
if (cmp(temp, paiwei[p])) {
paiwei[p + 1] = paiwei[p];
}
else
break;
}
paiwei[p + 1] = temp;
}

void myMergeSort(int* data, int num) {
if (num == 0) return;
else if (num == 1) return;

myMergeSort(data, num / 2);
myMergeSort(data + num / 2, num - num / 2);

//合并
int* temp = new int[num];

for (int i = 0, j = num / 2, n = 0; i < num / 2 || j < num; n++) {
if (i < num / 2 && j < num) {
if (cmp(data[i], data[j])) {
temp[n] = data[i];
i++;
}
else {
temp[n] = data[j];
j++;
}
}
else if (i == num / 2) {
temp[n] = data[j];
j++;
}
else if (j == num) {
temp[n] = data[i];
i++;
}
}

//复制
for (int i = 0; i < num; i++)
data[i] = temp[i];

delete temp;
}

int main() {
int N, R;
scanf("%d %d", &N, &R);
N *= 2;
//srand(0);
for (int i = 1; i <= N; ++i) {
paiwei[i - 1] = i;
scanf("%lld", &mouse[i].val);
//mouse[i].val =  rand()%mod;
}
for (int i = 1; i <= N; ++i) {
scanf("%lld", &mouse[i].strength);
//mouse[i].strength = rand()%mod;
}

//排序
quick_sort(paiwei, paiwei + N, cmp);
//myMergeSort(paiwei, N);

//开始比赛
for (int i = 0; i < R; ++i) {
for (int step = 0; step < N; step += 2) {
if (mouse[paiwei[step]].strength < mouse[paiwei[step + 1]].strength) {
mouse[paiwei[step + 1]].val += 2;
arrange(step + 1);
}
else if (mouse[paiwei[step]].strength == mouse[paiwei[step + 1]].strength) {
++mouse[paiwei[step]].val;
++mouse[paiwei[step + 1]].val;
arrange(step);
arrange(step + 1);
}
else {
mouse[paiwei[step]].val += 2;
arrange(step);
}
}
}

for (int i = 0; i < N; ++i)
printf("%d ", paiwei[i]);

return 0;
}


## Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 2e5 + 100;

struct Mouse {
int id;
int score;
int strength;

bool operator<(const Mouse &right) {
if ((score < right.score) || (score == right.score && id > right.id)) {
return 1;
} else {
return 0;
}
}

bool operator>(const Mouse &right) {
if ((score > right.score) || (score == right.score && id < right.id)) {
return 1;
} else {
return 0;
}
}
};

void qSort(Mouse *, int, int);
void contest();
void bubble();

int n, R, N;
Mouse mice[maxN] = {0};

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

cin >> n >> R;

N = 2 * n;

for (int i = 1; i <= N; i++) {
mice[i].id = i;
cin >> mice[i].score;
}
for (int i = 1; i <= N; i++) {
cin >> mice[i].strength;
}

qSort(mice, 1, N);

for (int i = 0; i < R; i++) {
contest();
bubble();
}

for (int i = 1; i <= N; i++) {
cout << mice[i].id << ' ';
}

return 0;
}

void qSort(Mouse *nums, int l, int h) {
if (l >= h) {
return;
}
Mouse temp = nums[l];
int i = l, j = l + 1, mid;
for (; j <= h; j++) {
if (mice[j] > temp) {
Mouse temp = mice[j];
mice[j] = mice[++i];
mice[i] = temp;
}
}
mice[l] = mice[i];
mice[i] = temp;
qSort(nums, l, i - 1);
qSort(nums, i + 1, h);
}

void contest() {
int temp1, temp2;

for (int i = 1; i <= n; i++) {
temp1 = 2 * i - 1;
temp2 = 2 * i;

if (mice[temp1].strength > mice[temp2].strength) {
mice[temp1].score += 2;
} else if (mice[temp1].strength < mice[temp2].strength) {
mice[temp2].score += 2;
} else {
mice[temp1].score += 1;
mice[temp2].score += 1;
}
}
}

void bubble() {
for (int i = 2; i <= N; i++) {
bool flag = 1;
for (int j = 1; j <= N - i + 1; j++) {
if (mice[j + 1] > mice[j]) {
Mouse temp = mice[j + 1];
mice[j + 1] = mice[j];
mice[j] = temp;
flag = 0;
}
}
if (flag) {
break;
}
}
}


## q4x3's solution

/**
* 模拟
* 直接归并排序过不了
* 这种和一定的(1 + 1 = 0 + 2)
* 扫描交换三次即可全序
**/
#include <iostream>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

class mouse {
public:
int ind, p, s;
mouse():ind(0), p(0), s(0) {}
mouse(int _ind, int _p, int _s):ind(_ind), p(_p), s(_s) {}
mouse(const mouse &obj):ind(obj.ind), p(obj.p), s(obj.s) {}
bool operator<(const mouse &obj) {
if(p < obj.p) return 1;
if(p > obj.p) return 0;
if(p == obj.p) return (ind > obj.ind);
return 0;
}
};

int N, R;
mouse m[200233];

int main() {
cin >> N >> R;
for(int i = 0;i < 2 * N;++ i) {
cin >> m[i].p;
m[i].ind = i;
}
for(int i = 0;i < 2 * N;++ i)
cin >> m[i].s;
mergeSort(0, 2 * N, m);
for(int i = 0;i < R;++ i) {
for(int i = 0;i < 3;++ i)
for(int i = 0;i < 2 * N - 1;++ i) {
if(m[i] < m[i + 1]) continue;
mouse tmp = m[i + 1];
m[i + 1] = m[i];
m[i] = tmp;
}
for(int i = 0;i < 2 * N - 1;i += 2) {
if(m[i].s < m[i + 1].s) {
m[i + 1].p += 2;
continue;
}
if(m[i].s > m[i + 1].s) {
m[i].p += 2;
continue;
}
if(m[i].s == m[i + 1].s) {
m[i].p += 1;
m[i + 1].p += 1;
continue;
}
}
}
mergeSort(0, 2 * N, m);
for(int i = 2 * N - 1;i >= 0;-- i)
cout << m[i].ind + 1 << " ";
cout << endl;
}


## skyzh's solution

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

struct Mouse {
int p, s, id;
};

inline bool cmp(const Mouse& a, const Mouse& b) {
if (a.p == b.p) {
return a.id < b.id;
} else return a.p > b.p;
}

Mouse A[200000];

int main() {
int N, R;
scanf("%d%d", &N, &R);
N *= 2;
for (int i = 0; i < N; i++) {
scanf("%d", &A[i].p);
A[i].id = i + 1;
}
for (int i = 0; i < N; i++) {
scanf("%d", &A[i].s);
}
sort(A, A + N, cmp);
for (int i = 0; i < R; i++) {
for (int j = 0; j < N; j += 2) {
Mouse& a = A[j];
Mouse& b = A[j + 1];
int res = a.s - b.s;
if (res > 0) a.p += 2;
else if (res == 0) {
a.p++; b.p++;
}
else b.p += 2;
}
while (true) {
bool sorted = true;
for (int i = 0; i < N - 1; i++) {
if (!cmp(A[i], A[i + 1])) {
swap(A[i], A[i + 1]);
sorted = false;
}
}
if (sorted) break;
}
}
for (int i = 0; i < N; i++) {
printf("%d ", A[i].id);
}
printf("\n");
return 0;
}


## victrid's solution

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct mouse {
int number;
int score;
int strength;
};

mouse tmplist[200005];
mouse ml[200005];

mouse* MergeSort(mouse* list, int listSize) {
if (listSize == 1)
return list;
if (listSize == 2) {
if (list[0].score < list[1].score || (list[0].score == list[1].score && list[0].number > list[1].number)) {
mouse temp = list[0];
list[0]    = list[1];
list[1]    = temp;
return list;
}
return list;
}

mouse* llst = MergeSort(list, listSize / 2);
mouse* rlst = MergeSort(list + listSize / 2, listSize - listSize / 2);
int lct = 0, rct = 0;
while (lct + rct != listSize) {
if (((llst[lct].score > rlst[rct].score || (llst[lct].score == rlst[rct].score && llst[lct].number < rlst[rct].number)) && lct < listSize / 2) || rct >= listSize - listSize / 2) {
tmplist[lct + rct] = llst[lct];
lct++;
} else {
tmplist[lct + rct] = rlst[rct];
rct++;
}
}
memcpy(list, tmplist, listSize * sizeof(mouse));
return list;
}

int main() {
int N, R;
cin >> N >> R;
for (int i = 0; i < 2 * N; i++) {
ml[i].number = i + 1;
scanf("%d", &(ml[i].score));
}
for (int i = 0; i < 2 * N; i++) {
scanf("%d", &(ml[i].strength));
}
MergeSort(ml, 2 * N);
for (int i = 0; i < R; i++) {
for (int i = 0; i < 2 * N; i += 2) {
if (ml[i].strength > ml[i + 1].strength)
ml[i].score += 2;
if (ml[i].strength == ml[i + 1].strength)
ml[i].score++, ml[i + 1].score++;
if (ml[i].strength < ml[i + 1].strength)
ml[i + 1].score += 2;
}
MergeSort(ml, 2 * N);
}
for (int i = 0; i < 2 * N; i++) {
if (i)
printf("%c",' ');
printf("%d",ml[i].number);
}
return 0;
}