sjtu_OJ/1593.cpp at master · q4x3/sjtu_OJ · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/**
 * 模拟
 * 直接归并排序过不了
 * 这种和一定的(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;
}