QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#633341	#4925. Adjacent Pairs	yjs_	0	3ms	16112kb	C++14	2.3kb	2024-10-12 15:07:55	2024-10-12 15:07:57

Judging History

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

[2024-10-12 15:07:57]
评测

测评结果：0
用时：3ms
内存：16112kb

查看

[2024-10-12 15:07:55]
提交

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;
}
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=1;i+1<=n;i+=2)
        {
            nxt[a[i+1]].push_back(a[i]);
            cntpr[mkp(a[i+1],a[i])]++;
        }
        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<<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<<endl; 
			}
            for(auto y:nxt[i])
                book[y]=0;
            nxt[i].clear();
            book[i]=0;
        }
        cntpr.clear();
        for(int i=3;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)]);
            }
            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);
            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[i][0]=cnt[i][1]=0;
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 20

Accepted

time: 3ms

memory: 16112kb

input:

output:

3
0

result:

ok 2 lines

Test #2:

score: 20

Accepted

time: 3ms

memory: 14212kb

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: 16112kb

input:

1
7
6 5 4 1 2 6 5

output:

result:

ok single line: '5'

Test #4:

score: 20

Accepted

time: 3ms

memory: 14028kb

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

Wrong Answer

time: 0ms

memory: 14216kb

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:

wrong answer 2nd lines differ - expected: '9', found: '7'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 0

Skipped

Dependency #1:

Subtask #4:

score: 0

Skipped