11593: 【原1593】Mouse

题目

题目描述

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

Description

隔壁村的阿黑的Mouse跑了, 于是Mouse变成了野生Mouse.

野生Mouse之间有着严格的等级秩序, 每隔一段时间就会举办一场大型的野生Mice比赛.

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

每轮比赛的对阵安排与该轮比赛开始前的排名有关：第 1 名和第 2 名、第 3 名和第 4 名...第 2K - 1 名和第 2K 名...第 2N - 1 名和第2N名,各进行一场比赛.

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

现给定每个野生Mouse的初始分数及其力量值，试计算在 R 轮比赛过后，所有野生Mouse的排名。

Input Format

输入的第一行是两个由空格隔开的正整数N, R, 含义如上.

第二行是 2N 个由空格隔开的非负整数{P}, 表示每只Mouse的初始分数.

第三行是 2N 个由空格隔开的非负整数{S}, , 表示每只Mouse的力量值.

Output Format

按排名从小到大输出R轮比赛后2N只野生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;
}