QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56513#4925. Adjacent Pairsnamelessgugugu0 3ms5396kbC++142.0kb2022-10-19 21:06:362022-10-19 21:06:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-19 21:06:37]
  • 评测
  • 测评结果：0
  • 用时：3ms
  • 内存：5396kb
查看
  • [2022-10-19 21:06:36]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
const int N = 200005;
int Test;
int n, a[N];
std::pair<int, int> cnt[2][N];
struct node
{
    int val;
    std::pair<int, int> pos;
    inline bool operator<(node b) const
    {
        return val == b.val ? pos < b.pos : val < b.val;
    }
};
std::set<node> st;
std::map<std::pair<int, int>, int> extra;
int main(void)
{
    scanf("%d", &Test);
    while(Test--)
    {
        scanf("%d", &n);
        for (int i = 0; i <= n;++i)
            cnt[0][i] = cnt[1][i] = {0, i};
        st.clear(), extra.clear();
        for (int i = 0; i < n; ++i)
            scanf("%d", a + i), ++cnt[i & 1][a[i]].first;
        for (int i = 0; i < n - 1;++i)
            if(i & 1)
                ++extra[{a[i], a[i + 1]}];
            else
                ++extra[{a[i + 1], a[i]}];
        for (int i = 0; i <= n; ++i)
            cnt[0][i].first = (n + 1) / 2 - cnt[0][i].first, cnt[1][i].first = n / 2 - cnt[1][i].first;
        std::sort(cnt[0], cnt[0] + n + 1);
        std::sort(cnt[1], cnt[1] + n + 1);
        st.insert({cnt[0][0].first + cnt[1][0].first, {0, 0}});
        int ans = 0x3f3f3f3f;
        while (1)
        {
            node now = *st.begin();
            st.erase(st.begin());
            int l = cnt[0][now.pos.first].second, r = cnt[1][now.pos.second].second;
            if(l != r)
            {
                if(!extra.count({l, r}))
                {
                    ans = std::min(ans, now.val);
                    break;
                }
                ans = std::min(ans, now.val + extra[{l, r}]);
            }
            int nl = now.pos.first, nr = now.pos.second;
            st.insert({cnt[0][nl + 1].first + cnt[1][nr].first, {nl + 1, nr}});
            st.insert({cnt[0][nl].first + cnt[1][nr + 1].first, {nl, nr + 1}});
        }
        printf("%d\n", ans);
    }
    return 0;
}
源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 0ms
memory: 3184kb

input:

2
5
4 5 2 4 5
2
1 2

output:

3
0

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 5216kb

input:

1
9
1 2 1 2 3 1 2 1 2

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5320kb

input:

1
7
6 5 4 1 2 6 5

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 2ms
memory: 5328kb

input:

1
16
4 3 4 3 4 3 4 3 1 4 3 4 1 4 3 4

output:

10

result:

ok single line: '10'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5308kb

input:

9
11
1 4 5 7 9 2 10 3 11 6 8
11
10 7 11 4 3 6 9 2 8 1 5
11
11 9 8 10 1 7 5 4 3 6 2
11
9 10 6 11 5 1 8 7 2 4 3
11
11 6 2 1 10 4 3 8 7 9 5
11
5 10 4 9 6 1 2 7 8 11 3
11
7 9 8 11 6 1 4 5 2 3 10
11
10 3 11 2 6 1 9 7 4 5 8
12
10 9 4 7 11 6 8 12 2 1 3 5

output:

9
9
9
9
9
9
9
9
10

result:

ok 9 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 5196kb

input:

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

output:

17
18
18
18
18

result:

ok 5 lines

Test #7:

score: 0
Accepted
time: 2ms
memory: 5380kb

input:

2
49
21 4 18 35 34 39 9 48 16 33 31 7 10 12 41 40 8 14 2 22 30 24 44 27 42 29 37 17 23 45 32 46 1 26 28 5 25 49 43 6 38 19 11 36 15 47 13 3 20
50
18 4 7 46 39 37 9 20 48 14 3 35 32 43 17 11 31 8 28 26 1 36 6 21 27 12 24 44 29 15 42 38 22 23 45 25 33 2 13 34 41 19 47 49 5 10 40 16 50 30

output:

47
48

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 2ms
memory: 5324kb

input:

10
10
1 3 8 5 9 10 6 4 2 7
10
8 2 1 10 9 4 6 7 5 3
10
5 7 6 8 2 10 9 3 4 1
10
6 1 2 7 9 10 5 3 8 4
10
7 5 2 6 4 1 3 10 9 8
10
2 4 3 1 5 8 7 10 6 9
10
1 9 2 4 5 6 7 10 3 8
10
4 10 7 5 1 3 6 8 9 2
10
8 5 7 9 6 4 1 2 3 10
10
10 6 2 3 1 7 5 4 8 9

output:

8
8
8
8
8
8
8
8
8
8

result:

ok 10 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 5320kb

input:

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

output:

22
23
23
23

result:

ok 4 lines

Test #10:

score: 0
Accepted
time: 2ms
memory: 5364kb

input:

1
100
91 92 11 30 28 52 95 76 9 21 70 8 89 84 10 37 83 39 97 16 18 2 27 48 58 78 74 72 15 44 7 4 98 45 63 29 55 49 31 13 17 56 32 14 62 93 24 100 12 6 20 94 79 66 22 19 73 67 25 3 57 42 54 60 5 90 64 53 23 80 40 59 34 88 77 46 47 41 26 96 1 65 43 69 51 99 38 36 33 71 61 75 87 68 50 86 35 82 85 81

output:

98

result:

ok single line: '98'

Test #11:

score: 0
Accepted
time: 0ms
memory: 5212kb

input:

10
9
5 4 1 9 6 7 1 3 6
10
5 10 6 10 6 10 8 7 5 1
10
6 10 7 9 7 4 2 8 2 5
10
9 5 3 9 5 3 7 9 7 3
10
2 9 6 10 6 10 7 3 7 10
10
2 5 1 5 10 8 10 5 8 4
10
5 1 3 4 9 4 10 4 1 6
10
7 6 7 10 6 7 6 7 6 10
10
2 4 2 4 9 2 7 2 7 4
10
8 9 10 6 5 6 7 5 1 9

output:

6
5
7
6
5
5
6
5
5
7

result:

ok 10 lines

Test #12:

score: 0
Accepted
time: 1ms
memory: 5220kb

input:

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

output:

15
15
12
15
12

result:

ok 5 lines

Test #13:

score: 0
Accepted
time: 2ms
memory: 5308kb

input:

2
49
8 43 31 29 46 29 32 49 32 19 31 12 44 12 9 49 43 49 43 23 8 2 8 2 5 7 13 25 7 25 7 25 4 25 36 28 36 19 40 19 40 19 30 19 47 40 24 31 9
50
15 46 35 30 35 29 27 29 50 43 47 38 40 38 18 27 24 49 7 49 24 44 4 19 30 24 1 25 1 50 7 38 12 15 50 48 1 27 29 21 46 31 46 41 6 41 50 1 50 32

output:

41
43

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 2ms
memory: 5372kb

input:

9
11
5 9 5 9 6 7 6 10 7 10 6
11
4 8 7 4 10 4 10 5 8 5 8
11
3 11 3 8 3 11 8 11 8 3 11
11
2 6 10 6 2 11 2 11 5 7 11
11
6 4 7 4 7 4 7 4 8 9 6
11
5 11 3 11 4 11 5 8 3 8 4
11
8 3 5 8 5 8 3 5 8 5 8
11
5 3 8 4 1 10 1 6 8 10 3
11
11 5 8 5 4 7 5 7 5 10 3

output:

6
7
6
6
4
6
8
7
7

result:

ok 9 lines

Test #15:

score: 0
Accepted
time: 0ms
memory: 3264kb

input:

4
24
21 15 5 22 13 14 13 21 18 6 18 6 18 4 19 4 19 10 5 9 21 9 12 24
25
8 14 15 14 15 14 18 17 18 17 21 19 25 1 9 1 15 4 15 4 23 13 19 15 19
25
25 20 15 12 20 12 6 23 25 12 8 15 12 7 20 14 6 12 11 25 8 23 6 8 23
25
7 24 21 17 15 16 17 16 9 21 4 24 15 23 20 17 18 23 3 21 3 7 20 18 5

output:

19
18
18
21

result:

ok 4 lines

Test #16:

score: 0
Accepted
time: 2ms
memory: 5200kb

input:

1
100
34 15 81 15 81 15 81 15 81 15 81 88 16 88 16 88 16 67 87 67 87 67 87 67 87 67 6 62 53 83 53 83 53 83 53 83 53 49 69 49 69 49 69 90 59 90 37 94 37 94 37 94 37 6 55 6 55 89 87 89 87 41 73 8 73 8 73 8 73 8 15 68 9 68 35 76 35 76 35 76 35 76 35 76 40 81 40 81 40 81 40 81 40 31 79 31 79 31 79 31

output:

89

result:

ok single line: '89'

Test #17:

score: 0
Accepted
time: 3ms
memory: 5324kb

input:

10
10
1 9 1 9 1 9 7 1 9 2
10
8 1 8 1 8 1 6 8 1 7
10
10 4 10 4 10 4 1 10 4 2
10
2 4 2 4 2 4 9 2 4 5
10
8 1 8 1 8 1 7 8 1 3
10
5 2 5 2 5 2 1 5 2 7
10
7 9 7 9 7 9 6 7 9 4
10
5 7 5 7 5 7 9 5 7 4
10
4 10 4 10 4 10 1 4 10 8
10
3 10 3 10 3 10 1 3 10 6

output:

5
5
5
5
5
5
5
5
5
5

result:

ok 10 lines

Test #18:

score: 0
Accepted
time: 2ms
memory: 5236kb

input:

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

output:

14
15
15
15
15

result:

ok 5 lines

Test #19:

score: 0
Accepted
time: 0ms
memory: 5396kb

input:

2
50
49 10 49 10 49 10 11 49 10 3 19 3 19 46 3 19 9 50 9 50 41 9 50 37 12 37 12 31 37 12 14 18 14 18 29 14 18 27 7 27 7 45 27 7 20 48 4 38 5 2
50
44 19 44 19 44 19 33 44 19 17 3 17 3 34 17 3 6 26 6 26 7 6 26 23 35 23 35 45 23 35 2 13 2 13 48 2 13 8 49 8 49 24 8 49 4 42 9 20 12 36

output:

45
45

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 2ms
memory: 5316kb

input:

10
10
1 9 1 9 1 9 6 1 9 10
10
5 9 5 9 5 9 3 5 9 8
10
7 2 7 2 7 2 9 7 2 6
10
1 7 1 7 1 7 10 1 7 8
10
10 6 10 6 10 6 7 10 6 1
10
2 8 2 8 2 8 1 2 8 10
10
3 1 3 1 3 1 7 3 1 2
10
5 2 5 2 5 2 3 5 2 4
10
6 4 6 4 6 4 10 6 4 9
10
3 6 3 6 3 6 10 3 6 9

output:

5
5
5
5
5
5
5
5
5
5

result:

ok 10 lines

Test #21:

score: 0
Accepted
time: 2ms
memory: 3268kb

input:

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

output:

19
20
20
20

result:

ok 4 lines

Test #22:

score: 0
Accepted
time: 0ms
memory: 5332kb

input:

1
99
26 90 26 90 26 90 13 26 90 3 63 3 63 94 3 63 25 5 25 5 21 25 5 29 30 29 30 85 29 30 69 82 69 82 22 69 82 88 97 88 97 42 88 97 62 66 62 66 72 62 66 73 28 73 28 24 73 28 92 47 92 47 80 92 47 51 38 51 38 23 51 38 14 84 14 84 11 14 84 18 43 18 43 55 18 43 19 49 19 49 99 19 49 8 91 34 17 9 70

output:

94

result:

ok single line: '94'

Test #23:

score: 0
Accepted
time: 2ms
memory: 5304kb

input:

9
11
4 9 11 9 6 7 1 6 2 1 6
11
9 11 8 4 8 11 5 9 1 5 9
11
2 6 8 11 2 8 10 5 1 10 5
11
3 7 2 3 2 8 1 6 2 1 6
11
6 9 1 9 5 4 3 8 1 3 8
11
2 8 3 5 9 11 1 4 2 1 4
11
6 11 1 6 7 11 9 11 1 9 11
11
4 3 1 5 1 8 4 10 1 4 10
11
6 2 11 7 6 2 6 10 1 6 10

output:

7
7
8
7
7
8
6
7
6

result:

ok 9 lines

Test #24:

score: 0
Accepted
time: 1ms
memory: 5360kb

input:

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

output:

15
16
15
16
16

result:

ok 5 lines

Test #25:

score: 0
Accepted
time: 2ms
memory: 5216kb

input:

2
50
37 28 35 42 1 30 21 22 29 34 46 27 22 10 27 22 49 36 37 33 19 46 2 15 47 31 43 31 43 31 43 31 43 31 43 31 43 1 31 43 31 43 31 43 31 43 31 43 31 43
50
23 14 9 13 18 16 35 25 41 43 50 40 50 39 6 39 30 20 49 11 14 7 17 42 4 17 23 17 23 17 23 17 23 17 23 17 23 1 17 23 17 23 17 23 17 23 17 23 17 23

output:

42
41

result:

ok 2 lines

Test #26:

score: 0
Accepted
time: 2ms
memory: 5216kb

input:

10
10
4 8 5 2 4 9 8 1 9 8
10
3 10 8 7 3 2 8 1 2 8
10
10 9 2 3 6 7 6 1 7 6
10
3 10 6 8 5 4 10 1 4 10
10
8 2 8 2 3 5 7 1 5 7
10
4 2 10 9 10 5 8 1 5 8
10
9 2 8 9 6 7 6 1 7 6
10
6 7 4 1 3 2 4 1 2 4
10
8 5 1 3 1 9 2 1 9 2
10
9 4 5 4 10 4 5 1 4 5

output:

6
7
7
7
6
7
7
6
7
6

result:

ok 10 lines

Test #27:

score: 0
Accepted
time: 3ms
memory: 5196kb

input:

4
25
23 12 23 14 10 19 17 2 25 18 11 7 10 7 10 7 10 7 1 10 7 10 7 10 7
25
6 10 3 22 18 23 11 2 8 10 15 3 14 10 14 10 14 10 1 14 10 14 10 14 10
25
7 13 3 16 14 6 4 16 21 8 5 20 17 1 17 1 17 1 2 17 1 17 1 17 1
25
11 8 3 8 21 20 1 2 17 15 17 3 7 21 7 21 7 21 1 7 21 7 21 7 21

output:

19
19
20
19

result:

ok 4 lines

Test #28:

score: 0
Accepted
time: 2ms
memory: 5372kb

input:

1
99
87 35 81 77 78 24 83 46 65 1 27 46 40 91 90 47 43 52 15 73 22 92 99 11 10 76 65 39 20 93 44 57 87 71 96 33 1 40 30 64 61 60 33 31 43 62 78 59 68 90 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 1 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78 81 78

output:

83

result:

ok single line: '83'

Test #29:

score: 0
Accepted
time: 2ms
memory: 5196kb

input:

10
9
2 3 7 8 3 7 3 7 3
10
3 7 6 7 6 10 7 6 10 7
10
6 4 7 4 7 4 7 4 8 4
10
1 2 3 2 6 2 6 2 6 2
10
10 6 2 6 2 6 2 6 2 8
10
3 7 6 7 6 7 6 10 7 6
10
7 6 8 6 4 8 6 4 6 4
10
6 2 4 2 4 2 4 2 4 1
10
2 5 4 5 6 5 4 5 4 6
10
5 4 7 4 7 4 7 4 7 4

output:

5
6
2
2
2
5
7
2
3
1

result:

ok 10 lines

Test #30:

score: -20
Wrong Answer
time: 2ms
memory: 3368kb

input:

5
20
19 20 4 20 4 20 4 20 8 20 8 20 4 8 20 4 20 8 20 8
20
10 14 6 14 6 14 6 4 14 6 14 6 14 6 4 14 6 14 6 14
20
17 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 18 12 18
20
6 4 2 20 4 2 4 2 4 2 20 4 20 4 20 4 2 4 2 20
20
7 14 20 14 20 14 20 14 20 14 20 14 16 14 20 14 20 14 20 16

output:

12
13
4
13
3

result:

wrong answer 1st lines differ - expected: '11', found: '12'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2024-12-11 22:25:38 | 開源專案