QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #105689 | #4791. Movies | Determinant | WA | 3ms | 3756kb | C++14 | 1.0kb | 2023-05-14 21:20:22 | 2023-05-14 21:20:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;const int N=1e5+7;
int n,m,ans=1e9,minn=1e9,fl=1,a[N],b[N],c[N];
int sum(int x){return x==n?m:a[c[x]]-x;}
int sum(int x,int y){return sum(y)-sum(x);}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){scanf("%d",&a[i]);b[i]=a[i];if(a[i]>a[i-1])fl=0;}
if(fl){puts("0");return 0;}sort(b+1,b+n+1);
for(int i=1;i<=n;++i)c[lower_bound(b+1,b+n+1,a[i])-b]=i;
for(int r=1,l=1;r<n;++r){
if(c[r]<c[r-1])l=r;int x=max(2*(l-1)-1,2*(n-1-r)),L,R,fl;
if(sum(l-1,r+1)>=x)ans=min(ans,x);
else{
x=sum(l-1,r+1),fl=(x+1)%2;
L=max(l-1-(x+1)/2,0);
R=max(n-1-r-x/2,0);
if(!L){if(sum(0,l-1)>=R*2-(fl==0))ans=min(ans,x+R*2-(fl==0));}
else if(!R){if(sum(r+1,n)>=L*2-(fl==1))ans=min(ans,x+R*2-(fl==0));}
else{
if(sum(r+1,n)>=L*2-(fl==1)&&sum(0,l-1)>=L*2-(fl==1)+R*2-1)
ans=min(ans,x+L*2-(fl==1)+R*2-1);
if(sum(0,l-1)>=R*2-(fl==0)&&sum(r+1,n)>=R*2-(fl==0)+L*2-1)
ans=min(ans,x+R*2-(fl==0)+L*2-1);
}
}
}
printf("%d\n",ans==1e9?-1:ans+1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3532kb
input:
5 5 3 1 5 2 4 6 8 7 9 10
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
5 10 3 5 9 15 4 6 11 13 1 7 10 12 14 2 8
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
5 10 14 15 4 12 1 3 9 6 10 13 2 11 7 5 8
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
10 10 13 10 4 11 2 15 14 16 1 17 20 18 8 19 6 5 3 9 12 7
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
10 10 20 3 17 8 10 6 18 15 14 19 11 9 13 16 4 7 12 5 1 2
output:
9
result:
ok 1 number(s): "9"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
8 12 1 6 20 13 3 5 9 17 7 2 14 11 19 16 12 18 4 15 10 8
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3572kb
input:
10 10 9 6 16 10 18 5 20 17 13 1 14 8 19 2 12 11 3 7 4 15
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
10 10 7 2 19 5 20 4 14 15 9 16 17 8 12 11 13 10 1 3 6 18
output:
9
result:
ok 1 number(s): "9"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
10 10 9 20 2 13 15 10 16 19 1 4 3 11 7 14 12 8 6 17 18 5
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
10 10 10 14 6 7 11 8 18 19 15 12 5 17 20 16 2 1 9 4 3 13
output:
-1
result:
ok 1 number(s): "-1"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
50 100 115 22 37 125 124 62 47 145 88 126 134 127 77 121 148 25 120 21 42 17 75 138 144 76 109 13 78 82 102 5 32 143 52 72 69 18 67 92 133 56 9 38 89 15 61 7 137 6 1 58 107 147 54 98 73 31 3 40 71 87 140 136 2 60 130 44 50 59 93 90 70 36 149 105 11 68 63 79 119 96 106 8 30 51 108 94 141 12 122 14 49...
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
50 100 69 63 30 79 36 27 46 57 28 98 19 15 18 75 77 76 86 74 131 78 60 33 11 40 24 116 71 109 23 111 99 87 58 103 132 119 55 66 122 54 128 43 130 147 94 125 90 144 105 148 89 51 41 84 81 88 100 12 82 17 118 126 93 143 101 64 145 3 134 5 13 62 7 6 133 31 26 138 16 2 129 110 65 102 108 114 35 10 115 9...
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
50 100 72 7 130 30 87 104 4 32 11 46 111 49 35 124 12 67 36 26 13 143 45 92 33 8 125 148 59 127 114 55 68 41 98 83 19 99 108 28 47 115 90 135 15 56 65 48 93 101 138 84 22 6 121 40 57 53 37 105 116 34 21 75 64 80 70 16 5 91 73 9 103 25 2 71 58 61 86 133 120 137 150 126 94 134 119 147 97 82 18 145 42 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 3ms
memory: 3744kb
input:
50 100 32 24 115 62 144 61 118 21 84 68 9 30 114 79 27 19 147 75 35 73 4 90 71 111 140 18 88 81 26 102 59 78 77 103 16 138 12 33 145 150 44 148 107 28 11 42 124 109 143 128 38 31 131 97 58 104 25 76 41 15 74 43 53 110 85 70 57 91 92 80 86 5 83 64 96 116 95 133 93 1 105 139 66 141 37 23 14 50 106 113...
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
50 100 105 22 115 6 88 101 42 41 18 111 39 4 63 3 52 142 84 48 119 85 89 110 73 86 53 143 117 129 62 30 98 116 40 25 123 113 130 103 45 95 128 75 148 106 145 38 20 125 118 82 81 23 15 55 8 9 92 77 91 2 144 97 132 11 147 102 33 137 71 121 133 29 107 27 1 99 134 93 90 21 112 50 28 26 24 114 96 12 122 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
50 100 2 29 6 31 23 19 4 10 36 32 69 78 50 24 13 92 61 58 70 18 110 42 56 99 129 26 43 91 75 86 115 97 95 102 64 53 117 88 139 145 108 132 147 149 121 150 116 138 142 146 65 80 123 126 93 136 89 113 74 106 94 52 125 134 77 111 48 118 87 144 41 49 71 109 17 5 40 25 33 82 39 62 30 7 141 8 9 21 28 45 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #17:
score: -100
Wrong Answer
time: 2ms
memory: 3548kb
input:
50 100 2 5 9 12 14 15 20 21 22 26 33 30 34 36 38 42 44 43 47 49 48 55 57 60 67 69 75 79 78 81 82 85 90 100 91 99 108 109 112 116 124 115 119 125 127 129 143 148 147 150 17 16 80 102 11 3 25 142 23 137 131 7 123 110 54 65 118 113 19 149 92 56 29 46 31 70 96 77 106 146 120 53 37 84 95 134 141 139 72 7...
output:
60
result:
wrong answer 1st numbers differ - expected: '80', found: '60'