QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359048 | #5076. Prof. Pang and Ants | wdnmdwrnmmp | TL | 6194ms | 3856kb | C++14 | 1.6kb | 2024-03-20 11:30:32 | 2024-03-20 11:30:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1e18;
void solve(){
int n,m; cin>>n>>m;
vi a(n),b(n);
rep(i,0,n-1){
cin>>a[i];
}
auto chk=[&](int mid){
auto cchk=[&]()->int{
vector< array<int,2> > msg;
rep(i,0,n-1){
msg.pb({1+a[i],1});
msg.pb({b[i]+a[i]+1,-1});
msg.pb({b[i]+1-a[i]-1,2});
msg.pb({mid-a[i]+1-1,-2});
}
sort(msg.begin(),msg.end());
int res=0,rst=0,ls=-inf;
int cnt0=0,cnt1=0;
for(auto x:msg){
int t=x[0]-ls;
res+=t*min(cnt0,cnt1);
int nxt=max(0ll, rst+(cnt0-cnt1)*t );
if(nxt<rst){
res+=rst-nxt;
}
rst=nxt,ls=x[0];
if(x[1]==1){
cnt0++;
}
else if(x[1]==-1){
cnt0--;
}
else if(x[1]==2){
cnt1++;
}
else{
cnt1--;
}
}
return res>=m;
};
auto dfs=[&](auto self,int d)->int{
if(d==n){
if(cchk()){
return 1;
}
return 0;
}
rep(x,mid/2,(mid+1)/2){
b[d]=x;
if(self(self,d+1)){
return 1;
}
}
return 0;
};
return dfs(dfs,0);
};
int l=0,r=(*max_element(a.begin(),a.end())+m/n+1)*2;
while(l<r){
int mid=(l+r)/2;
if(chk(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l<<'\n';
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
3 2 4 1 2 3 10 1 2 3 5 1 1 2 3 4 5
output:
6 9 4
result:
ok 3 number(s): "6 9 4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 1 100000000000000 1000000000
output:
200000000000000
result:
ok 1 number(s): "200000000000000"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
1 10 1 1 1 1 1 1 1 1 1 1 1
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 101ms
memory: 3856kb
input:
100000 1 76 95 1 60 68 1 81 86 1 88 67 1 69 28 1 75 65 1 56 22 1 88 60 1 51 41 1 64 11 1 54 71 1 63 19 1 88 5 1 89 66 1 80 66 1 81 48 1 67 99 1 94 36 1 54 46 1 51 37 1 82 17 1 74 41 1 69 61 1 79 65 1 78 10 1 71 17 1 87 88 1 83 2 1 58 29 1 59 43 1 78 53 1 75 73 1 77 71 1 52 82 1 63 69 1 83 19 1 61 27...
output:
267 197 254 223 138 206 112 209 134 128 197 126 176 222 213 178 266 188 147 126 164 157 192 210 156 142 264 166 117 146 185 222 220 217 202 166 122 162 250 214 160 158 220 132 108 213 198 276 226 197 204 140 146 215 122 142 201 269 269 188 144 246 251 200 217 184 192 139 234 128 190 242 254 166 152 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 201ms
memory: 3756kb
input:
100000 2 87 72 38 2 73 58 25 2 84 71 78 2 91 83 34 2 56 26 24 2 63 97 73 2 67 11 91 2 56 44 55 2 67 34 53 2 93 19 72 2 55 29 91 2 78 2 70 2 56 28 83 2 77 33 5 2 98 60 76 2 63 82 59 2 82 50 72 2 73 91 40 2 85 97 41 2 60 35 14 2 86 51 74 2 61 52 37 2 96 35 45 2 85 23 15 2 96 45 92 2 96 76 4 2 58 55 98...
output:
155 121 192 160 79 203 114 128 122 132 114 101 113 78 186 174 164 154 168 80 169 121 129 85 186 118 169 207 114 166 165 150 98 129 183 171 225 158 117 94 88 190 119 128 187 112 187 184 138 177 166 149 76 179 125 102 64 99 188 185 126 128 88 80 87 150 127 191 102 166 214 96 116 122 187 206 120 122 98...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 335ms
memory: 3488kb
input:
100000 3 87 37 25 86 3 94 64 78 24 3 55 89 60 41 3 64 54 100 33 2 74 13 95 2 83 89 17 2 51 81 64 2 97 1 91 3 82 41 61 94 3 66 3 50 46 3 84 49 45 48 2 62 6 54 3 67 6 73 7 2 95 44 48 3 80 84 21 42 2 94 11 97 2 79 98 87 3 91 44 31 21 2 84 63 15 3 75 80 57 96 2 87 93 74 2 74 69 19 2 80 18 38 2 96 87 30 ...
output:
107 136 130 120 122 127 172 127 144 78 124 82 67 141 104 136 226 96 115 176 212 113 97 157 132 140 104 105 116 174 116 114 91 85 166 133 94 70 185 104 140 117 90 168 116 108 152 127 130 167 97 155 87 76 225 136 149 103 75 187 161 104 98 113 81 120 112 94 97 130 156 60 97 95 200 100 132 89 147 126 21...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 704ms
memory: 3496kb
input:
100000 4 90 14 97 74 38 4 54 21 15 46 16 3 86 95 74 59 3 86 42 64 31 3 66 94 100 60 3 83 92 13 77 3 81 80 32 9 3 52 42 48 41 4 64 90 68 23 1 3 76 80 71 1 4 79 7 71 17 86 4 81 22 1 20 96 3 68 70 28 54 4 87 27 1 66 51 3 65 47 74 55 4 87 6 14 56 89 3 96 64 57 64 3 52 25 95 48 4 85 98 71 33 8 3 59 3 1 5...
output:
98 54 177 117 187 116 83 106 64 100 79 59 117 78 136 75 157 100 85 59 64 119 129 127 134 159 88 101 172 87 124 56 101 91 130 109 76 70 113 127 65 145 112 85 126 88 157 162 98 98 119 131 71 101 106 102 64 130 144 138 106 144 96 76 95 70 82 86 109 43 172 64 100 88 97 64 165 74 97 163 87 74 126 62 110 ...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 1182ms
memory: 3796kb
input:
100000 3 52 91 84 66 3 55 47 65 9 5 93 20 100 49 93 100 5 68 51 47 88 33 33 4 62 26 65 53 80 4 85 88 52 51 70 5 79 66 27 7 29 87 5 84 86 82 11 45 23 5 67 43 87 96 62 79 3 99 85 59 49 3 59 19 20 57 5 64 73 18 62 57 61 5 96 10 11 7 1 79 3 63 77 57 6 3 93 13 76 22 5 71 18 72 37 72 19 4 91 54 51 70 88 5...
output:
177 75 117 99 111 145 70 77 140 159 70 101 48 85 92 74 148 117 64 123 54 101 86 50 108 105 169 100 66 85 53 98 113 86 130 99 115 75 87 62 131 88 72 113 96 87 73 88 106 197 106 87 79 93 99 104 129 81 82 73 100 84 96 132 84 91 93 158 169 89 67 118 84 73 95 87 118 48 90 104 107 119 89 66 93 56 62 110 1...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 2113ms
memory: 3552kb
input:
83333 6 55 56 67 50 53 91 87 5 99 16 62 37 23 4 5 53 100 45 65 26 45 6 54 12 32 96 87 36 75 5 90 84 82 26 11 34 5 85 16 61 18 63 37 6 100 48 25 1 9 29 63 6 70 17 17 96 31 8 21 5 80 32 94 43 19 91 5 51 88 29 41 92 9 5 53 26 62 51 31 7 5 81 45 3 56 26 81 5 79 83 78 24 26 20 4 88 89 33 92 49 5 90 79 77...
output:
126 64 96 72 79 77 58 50 91 65 61 74 74 127 106 61 44 58 61 169 126 71 116 108 41 75 111 97 88 50 108 113 72 115 100 98 70 78 93 91 80 64 125 64 76 59 96 107 69 92 71 75 112 88 100 148 105 79 80 68 83 46 56 96 40 88 44 79 67 85 84 54 84 86 78 131 102 74 59 66 51 100 106 95 58 156 134 84 131 55 68 58...
result:
ok 83333 numbers
Test #10:
score: 0
Accepted
time: 3125ms
memory: 3492kb
input:
71428 4 67 32 43 42 20 4 81 56 97 53 77 5 87 62 29 93 48 31 5 60 6 62 75 69 45 6 64 2 70 14 99 96 12 4 53 41 23 99 97 6 65 47 49 14 18 7 42 7 52 45 55 16 61 38 64 100 6 76 60 26 15 93 79 63 5 67 24 83 11 37 13 5 65 19 6 30 17 8 4 77 73 95 17 54 4 57 18 42 86 52 6 68 42 71 17 12 70 7 4 86 88 2 78 44 ...
output:
86 151 102 75 43 92 49 81 80 56 43 111 90 48 90 126 117 59 87 54 72 79 59 81 95 78 105 72 59 85 132 99 122 76 51 117 122 75 46 74 61 145 116 84 110 114 78 76 135 89 93 64 77 67 68 100 78 152 81 98 157 89 158 58 48 71 170 90 77 70 112 44 52 103 70 48 96 58 45 67 63 60 38 56 107 48 83 121 101 112 58 1...
result:
ok 71428 numbers
Test #11:
score: 0
Accepted
time: 6194ms
memory: 3532kb
input:
62500 6 66 13 26 30 76 55 74 8 92 87 100 71 60 24 47 38 1 5 87 81 67 74 92 30 5 83 32 81 57 46 8 8 92 72 90 47 24 14 82 74 3 6 57 58 36 74 64 96 87 6 59 50 48 63 19 4 50 7 91 4 39 50 60 90 13 51 5 81 30 49 88 52 21 6 55 38 67 64 92 54 4 7 85 96 55 76 56 58 97 17 8 54 54 18 55 25 43 82 94 27 7 72 64 ...
output:
69 73 142 83 60 124 56 67 93 66 115 66 74 58 97 81 107 59 58 96 67 70 79 63 58 78 77 66 101 55 83 94 68 48 94 81 88 89 73 58 69 74 132 75 55 93 34 56 64 70 96 61 64 80 64 83 56 86 63 88 113 80 75 54 93 76 116 53 38 75 117 78 92 52 104 46 106 57 100 89 55 104 81 60 59 41 62 127 66 72 67 91 73 67 78 1...
result:
ok 62500 numbers
Test #12:
score: -100
Time Limit Exceeded
input:
55555 5 70 78 5 18 31 38 8 90 78 24 11 88 90 74 69 91 5 87 97 64 24 82 13 9 74 99 58 51 44 83 12 100 71 51 7 62 17 32 67 28 100 14 72 6 58 32 78 48 68 94 55 8 80 84 62 20 53 48 30 82 70 5 95 14 4 89 18 64 5 61 63 86 82 89 8 8 64 20 18 78 39 30 49 43 9 9 94 67 8 78 13 6 63 78 97 49 6 98 99 14 29 30 6...
output:
59 86 84 94 61 110 91 64 89 54 60 83 134 64 57 62 33 71 87 92 89 66 52 54 52 119 146 82 50 57 84 81 75 94 60 99 86 52 79 127 59 71 118 54 46 68 64 84 138 104 55 68 82 67 44 49 83 65 52 62 68 100 97 44 44 43 111 116 36 85 28 49 42 28 89 40 73 44 48 92 116 37 67 63 63 87 129 79 53 45 76 51 53 54 62 52...