QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#635123	#4925. Adjacent Pairs	yjs_	0	4ms	16256kb	C++14	2.8kb	2024-10-12 19:05:20	2024-10-12 19:05:20

Judging History

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

[2024-10-12 19:05:20]
评测

测评结果：0
用时：4ms
内存：16256kb

查看

[2024-10-12 19:05:20]
提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#define pr pair<int,int>
#define mkp make_pair
using namespace std;
const int N=300000;
int n,m,s,l,cnt[2][N],t,a[N];
vector<int>nxt[N];
map<pr,int>cntpr;
bool book[N];
struct qwq
{
    int val,cnt;
}p[N];
bool cmp(qwq a,qwq b)
{
    return a.cnt>b.cnt;
}
void CLEAR()
{
	for(int i=1;i<=n;i++)
	{
		cnt[0][i]=cnt[1][i]=0;
		a[i]=p[i].val=p[i].cnt=0;
		book[i]=0;
		nxt[i].clear();
	}
	cntpr.clear();
}
int main()
{
    scanf("%d",&t);
    for(;t;t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            cnt[i&1][a[i]]++;
        }
        cntpr.clear();
        for(int i=2;i+1<=n;i+=2)
        {
            nxt[a[i]].push_back(a[i+1]);
            cntpr[mkp(a[i],a[i+1])]++;
        }
        for(int i=1;i<=n;i++)
        {
            p[i].val=i;
            p[i].cnt=cnt[0][i];
        }
        sort(p+1,p+1+n,cmp);
        int ans=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            for(auto y:nxt[i])
            {
        	    book[y]=1;
                ans=min(ans,n-cnt[1][i]-cnt[0][y]+cntpr[mkp(i,y)]);
//                cout<<"op1: "<<i<<" "<<y<<" "<<ans<<" "<<cnt[1][i]<<" "<<cnt[0][y]<<" "<<cntpr[mkp(i,y)]<<endl;
            }
            book[i]=1;
            int now;
            for(now=1;book[p[now].val];now++);
            if(now<=n)
            {
                ans=min(ans,n-cnt[1][i]-p[now].cnt);
//            	cout<<"op2: "<<i<<" "<<p[now].val<<" "<<ans<<" "<<cnt[1][i]<<" "<<p[now].cnt<<endl; 
			}
            for(auto y:nxt[i])
                book[y]=0;
            nxt[i].clear();
            book[i]=0;
        }
        cntpr.clear();
        for(int i=2;i<=n;i+=2)
        {
            nxt[a[i]].push_back(a[i-1]);
            cntpr[mkp(a[i],a[i-1])]++;
        }
        for(int i=1;i<=n;i++)
        {
            for(auto y:nxt[i])
            {
                book[y]=1;
                ans=min(ans,n-cnt[1][i]-cnt[0][y]+cntpr[mkp(i,y)]);
//                cout<<"op1: "<<i<<" "<<y<<" "<<ans<<" "<<cnt[1][i]<<" "<<cnt[0][y]<<" "<<cntpr[mkp(i,y)]<<endl;
            }
            book[i]=1;
            int now;
            for(now=1;book[p[now].val];now++);
            if(now<=n)
            {
                ans=min(ans,n-cnt[1][i]-p[now].cnt);
//            	cout<<"op2: "<<i<<" "<<p[now].val<<" "<<ans<<" "<<cnt[1][i]<<" "<<p[now].cnt<<endl; 
			}
            for(auto y:nxt[i])
                book[y]=0;
            nxt[i].clear();
            book[i]=0;
        }
        cntpr.clear();
        printf("%d\n",ans);
        for(int i=1;i<=n;i++)
            cnt[0][i]=cnt[1][i]=0;
//        CLEAR();.
    }
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 20

Accepted

time: 0ms

memory: 14212kb

input:

output:

3
0

result:

ok 2 lines

Test #2:

score: 20

Accepted

time: 3ms

memory: 14140kb

input:

1
9
1 2 1 2 3 1 2 1 2

output:

result:

ok single line: '6'

Test #3:

score: 20

Accepted

time: 3ms

memory: 14156kb

input:

1
7
6 5 4 1 2 6 5

output:

result:

ok single line: '5'

Test #4:

score: 20

Accepted

time: 3ms

memory: 14160kb

input:

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

output:

result:

ok single line: '10'

Test #5:

score: 20

Accepted

time: 0ms

memory: 14148kb

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:

result:

ok 9 lines

Test #6:

score: 20

Accepted

time: 3ms

memory: 16204kb

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:

result:

ok 5 lines

Test #7:

score: 20

Accepted

time: 0ms

memory: 16256kb

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: 20

Accepted

time: 0ms

memory: 14212kb

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:

result:

ok 10 lines

Test #9:

score: 20

Accepted

time: 3ms

memory: 14144kb

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:

result:

ok 4 lines

Test #10:

score: 20

Accepted

time: 4ms

memory: 16152kb

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:

result:

ok single line: '98'

Test #11:

score: 20

Accepted

time: 3ms

memory: 14064kb

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:

result:

ok 10 lines

Test #12:

score: 20

Accepted

time: 0ms

memory: 14164kb

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:

result:

ok 5 lines

Test #13:

score: 20

Accepted

time: 0ms

memory: 14028kb

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

Wrong Answer

time: 0ms

memory: 16068kb

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:

result:

wrong answer 3rd lines differ - expected: '6', found: '5'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 0

Skipped

Dependency #1:

Subtask #4:

score: 0

Skipped