QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#151574	#2789. Sorting	AbdelmagedNour^#	20	30ms	22224kb	C++20	1009b	2023-08-27 01:45:58	2024-07-04 02:41:21

Judging History

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

[2024-07-04 02:41:21]
评测

测评结果：20
用时：30ms
内存：22224kb

查看

[2023-08-27 01:45:58]
提交

answer

#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#include "sorting.h"
bool check(int T,int N,int M,int S[],int X[],int Y[],int P[],int Q[]){
    vector<vector<int>>nxt(T+1,vector<int>(N));
    for(int i=0;i<N;i++)nxt[T][i]=i;
    for(int i=T-1;i>=0;i--){
        for(int j=0;j<N;j++){
            nxt[i][j]=nxt[i+1][j];
        }
        swap(nxt[i][X[i]],nxt[i][Y[i]]);
    }
    int a[N];
    for(int i=0;i<N;i++)a[i]=S[i];
    for(int i=0;i<T;i++){
        int j=0;
        swap(a[X[i]],a[Y[i]]);
        while(j<N&&a[j]==nxt[i+1][j])j++;
        if(j==N)P[i]=Q[i]=0;
        else P[i]=j,Q[i]=find(nxt[i+1].begin(),nxt[i+1].end(),a[j])-nxt[i+1].begin();
        swap(a[P[i]],a[Q[i]]);
    }
    return is_sorted(a,a+N);
}
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
    int l=1,r=M,res=1;
    while(l<=r){
        int md=(l+r)>>1;
        if(check(md,N,M,S,X,Y,P,Q))r=(res=md)-1;
        else l=md+1;
    }
    return res;
}

源文件, 语言: C++20

详细

Subtask #1:

score: 8

Accepted

Test #1:

score: 8

Accepted

time: 0ms

memory: 4072kb

input:

output:

1
0 0

result:

ok correct

Test #2:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

1
0 0

result:

ok correct

Test #3:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

output:

1
0 1

result:

ok correct

Test #4:

score: 0

Accepted

time: 0ms

memory: 3704kb

input:

output:

1
0 1

result:

ok correct

Test #5:

score: 0

Accepted

time: 0ms

memory: 3788kb

input:

output:

result:

ok correct

Test #6:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

2
0 1
0 4

result:

ok correct

Test #7:

score: 0

Accepted

time: 0ms

memory: 3728kb

input:

output:

result:

ok correct

Subtask #2:

score: 12

Accepted

Test #8:

score: 12

Accepted

time: 0ms

memory: 3656kb

input:

output:

1
0 0

result:

ok correct

Test #9:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

output:

1
0 0

result:

ok correct

Test #10:

score: 0

Accepted

time: 1ms

memory: 3916kb

input:

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

output:

result:

ok correct

Test #11:

score: 0

Accepted

time: 1ms

memory: 3940kb

input:

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

output:

result:

ok correct

Test #12:

score: 0

Accepted

time: 1ms

memory: 3908kb

input:

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

output:

result:

ok correct

Subtask #3:

score: 0

Wrong Answer

Test #13:

score: 16

Accepted

time: 0ms

memory: 3796kb

input:

output:

1
0 1

result:

ok correct

Test #14:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

2
0 4
1 2

result:

ok correct

Test #15:

score: 0

Accepted

time: 1ms

memory: 4000kb

input:

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

output:

result:

ok correct

Test #16:

score: -16

Wrong Answer

time: 1ms

memory: 3864kb

input:

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

output:

result:

wrong answer the final array is not sorted

Subtask #4:

score: 0

Skipped

Dependency #2:

100%

Accepted

Dependency #3:

Subtask #5:

score: 0

Wrong Answer

Test #28:

score: 0

Wrong Answer

time: 30ms

memory: 22224kb

input:

1800
530 1775 466 953 230 1179 944 752 990 1316 275 1029 158 152 1673 1706 172 115 599 1661 131 699 1112 454 551 1059 291 495 28 67 773 480 839 462 1210 757 879 285 439 3 1429 820 26 1023 942 199 356 625 1705 1421 144 1529 716 7 1485 1027 1599 696 517 1353 456 1389 273 1363 1414 1177 718 41 777 1621...

output:

result:

wrong answer the final array is not sorted

Subtask #6:

score: 0

Skipped