QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326587 | #8225. 最小值之和 | linrui | 36 | 57ms | 4728kb | C++14 | 2.9kb | 2024-02-13 15:00:10 | 2024-02-13 15:00:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using u64=unsigned long long;
using LF=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define CT const&
#define IL inline
#define PB push_back
template<class T>
IL void tomn(T &x,T CT y){y<x?x=y,0:0;}
template<class T>
IL void tomx(T &x,T CT y){y>x?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
const LF EPS=1e-10L;
IL int dcmp(LF x){return fabs(x)<=EPS?0:(x<0?-1:1);}
const LL INF=4e18L;
const int N=85;
int n,g[N];
namespace S1{
const int N=15;
LF a[N][N],x[N];
bool calc(){
int row=1;
F(i,1,n-1){
int p=-1;
F(j,row,n)if(dcmp(a[j][i]))p=j;
if(p==-1)continue;
F(j,i,n)swap(a[row][j],a[p][j]);
F(j,row+1,n){
LF x=a[j][i]/a[row][i];
F(k,i,n)a[j][k]-=x*a[row][k];
}++row;
}F(i,1,n-1)x[i]=0;
F(i,row,n)if(dcmp(a[i][n]))return 0;
G(i,row-1,1){
int p=1;
while(p<=n&&!dcmp(a[i][p]))++p;
if(p>n)continue;
x[p]=a[i][n]/a[i][p];
F(j,1,i-1)a[j][n]-=a[j][p]*x[p],a[j][p]=0;
}return 1;
}
bool main(){
int f[N]{},p[N]{};
F(i,1,n-1)p[i]=i;
do{
vector<int> vec{p+1,p+n};
if(vec==vector<int>{3,1,4,2,5,6}){
cerr<<"!!!\n";
}
F(i,0,N-1)F(j,0,N-1)a[i][j]=0;
F(i,1,n){
int mn;
mn=n+1;G(j,i-1,1)tomn(mn,p[j]),a[i][mn]+=1;
mn=n+1;F(j,i,n-1)tomn(mn,p[j]),a[i][mn]+=1;
G(j,n-1,2)a[i][j-1]+=a[i][j];
a[i][n]=g[i];
}if(calc()){
F(i,2,n-1)x[i]+=x[i-1];
F(i,2,n-1)if(dcmp(x[i]-x[i-1])<0)goto ED;
F(i,1,n-1)if(dcmp(x[i]-LL(x[i]+.5L)))goto ED;
F(i,1,n-1)f[i]=x[p[i]]+.5L;
F(i,1,n-1)if(f[i]<0)goto ED;
goto OK;
}ED:;
}while(next_permutation(p+1,p+n));
return 0;
OK:
puts("Yes");
F(i,1,n-1)printf("%d ",f[i]);
return 1;
}
}
namespace S2{
const int N=55,W=55;
using D=bitset<N*W+100>;
D f[N][N];
int ans[N];
void dfs(int l,int r,int i){
if(l==r)return;
F(m,l,r-1)F(x,0,100000){
if(i+x*(r-l)>n*W)break;
if(f[l][m][i+x*(r-l)]&&f[m+1][r][i+x*(r-l)]){
F(j,l,r-1)ans[j]+=x;
return dfs(l,m,i+x*(r-l)),dfs(m+1,r,i+x*(r-l));
}
}
}
bool main(){
G(l,n,1)F(r,l,n){
f[l][r]=D{};
if(l==r){
f[l][r][g[l]]=1;
// cerr<<l<<" "<<r<<" ";
// F(i,0,10)cerr<<f[l][r][i];
// cerr<<endl;
continue;
}
F(m,l,r-1){
D d=f[l][m]&f[m+1][r];
G(i,n*W,0){
if(!d[i])continue;
int j=i;
while(j>=0&&!f[l][r][j])
f[l][r][j]=1,j-=(r-l);
}
}
// cerr<<l<<" "<<r<<" ";
// F(i,0,10)cerr<<f[l][r][i];
// cerr<<endl;
}if(!f[1][n][0])return 0;
dfs(1,n,0),puts("Yes");
F(i,1,n-1)printf("%d ",ans[i]);
return 1;
}
}
int main(){
#ifdef LOCAL
freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
#endif
scanf("%d",&n);
F(i,1,n)scanf("%d",g+i);
if(!S2::main())
puts("No");
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 1ms
memory: 3820kb
input:
5 14 14 12 13 13
output:
Yes 14 0 6 7
result:
ok The answer is correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
5 11 11 10 5 5
output:
Yes 6 5 0 5
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
5 10 10 10 4 4
output:
Yes 5 5 0 4
result:
ok The answer is correct.
Test #6:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
5 10 10 8 5 5
output:
Yes 6 4 0 5
result:
ok The answer is correct.
Test #10:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
5 24 24 28 28 26
output:
Yes 6 6 9 7
result:
ok The answer is correct.
Test #11:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
5 5 5 22 31 31
output:
Yes 5 0 11 20
result:
ok The answer is correct.
Test #12:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
5 16 16 4 12 12
output:
Yes 16 0 2 10
result:
ok The answer is correct.
Test #14:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
5 29 29 24 26 26
output:
Yes 29 0 12 14
result:
ok The answer is correct.
Test #15:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
5 0 33 33 32 32
output:
Yes 0 33 0 32
result:
ok The answer is correct.
Test #16:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
5 6 7 7 6 6
output:
Yes 3 4 0 6
result:
ok The answer is correct.
Test #23:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
5 25 25 24 20 20
output:
Yes 13 12 0 20
result:
ok The answer is correct.
Test #24:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
1 233
output:
No
result:
ok The answer is correct.
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #35:
score: 15
Accepted
time: 0ms
memory: 3852kb
input:
8 16 16 8 8 9 9 6 6
output:
Yes 16 0 8 0 9 0 6
result:
ok The answer is correct.
Test #36:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
8 16 16 9 21 21 23 23 23
output:
Yes 16 0 3 15 1 10 10
result:
ok The answer is correct.
Test #37:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
8 10 10 15 15 15 10 10 5
output:
Yes 10 0 6 6 1 6 1
result:
ok The answer is correct.
Test #38:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
8 13 13 15 15 24 24 24 10
output:
Yes 13 0 7 2 9 9 2
result:
ok The answer is correct.
Test #39:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
8 5 13 16 25 25 24 4 4
output:
Yes 1 3 4 9 8 0 4
result:
ok The answer is correct.
Test #40:
score: -15
Wrong Answer
time: 0ms
memory: 3664kb
input:
8 1313 1695 1695 1129 1129 711 557 557
output:
No
result:
wrong answer Line 1 expected
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Test #77:
score: 25
Accepted
time: 47ms
memory: 4412kb
input:
49 28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4
output:
Yes 14 14 0 12 25 0 15 18 1 13 27 0 41 0 5 12 15 10 3 17 18 0 9 0 7 10 1 0 17 0 3 5 9 0 13 0 0 6 0 4 6 10 5 0 2 9 7 1
result:
ok The answer is correct.
Test #78:
score: 0
Accepted
time: 48ms
memory: 4468kb
input:
49 3 3 29 29 31 31 34 34 34 34 31 22 22 21 21 21 36 36 37 42 42 41 22 22 6 6 19 37 65 71 71 77 78 78 76 76 42 46 46 40 60 60 60 60 60 60 6 6 4
output:
Yes 3 0 29 0 31 0 34 0 17 14 1 10 9 0 21 0 36 0 11 14 13 2 14 0 6 0 4 10 24 30 1 36 37 0 76 0 21 25 0 20 40 0 60 0 60 0 4 2
result:
ok The answer is correct.
Test #79:
score: 0
Accepted
time: 48ms
memory: 4416kb
input:
49 18 18 18 16 16 59 61 64 64 57 57 78 78 78 78 81 92 92 92 92 89 81 47 64 64 63 59 65 65 63 52 52 34 34 33 8 13 13 17 17 14 16 19 19 13 13 18 18 18
output:
Yes 9 9 0 16 0 19 20 23 1 53 0 78 0 78 0 36 47 1 28 25 21 3 8 15 14 12 0 31 29 1 46 1 15 14 0 4 9 0 17 0 3 4 7 1 6 1 6 6
result:
ok The answer is correct.
Test #80:
score: 0
Accepted
time: 52ms
memory: 4464kb
input:
50 43 47 47 42 42 41 51 51 57 62 62 61 58 58 67 67 68 68 63 68 68 67 71 71 76 76 76 76 76 76 48 48 48 48 36 36 33 33 4 8 8 6 6 11 11 3 3 10 10 10
output:
Yes 20 24 1 20 19 0 51 0 19 22 21 0 58 0 67 0 68 0 21 24 23 0 71 0 76 0 76 0 76 0 48 0 48 0 36 0 33 0 2 6 0 6 0 11 0 3 0 5 5
result:
ok The answer is correct.
Test #81:
score: 0
Accepted
time: 48ms
memory: 4412kb
input:
49 12 14 14 16 16 10 18 32 32 30 30 0 0 5 5 4 0 9 9 18 18 18 30 41 43 43 39 39 35 24 26 27 27 6 6 13 13 19 22 22 21 21 44 44 43 43 33 33 31
output:
Yes 6 8 0 16 0 2 4 18 4 16 0 0 0 3 2 0 0 9 0 9 9 0 5 9 11 6 10 6 0 8 9 10 0 6 0 1 1 4 7 1 2 2 25 2 24 2 9 7
result:
ok The answer is correct.
Test #82:
score: 0
Accepted
time: 39ms
memory: 4448kb
input:
48 13 13 11 3 36 40 40 40 36 35 35 30 18 18 33 33 33 23 20 20 17 19 20 20 0 10 31 31 28 30 30 5 16 16 13 12 12 36 39 39 37 37 25 25 26 26 7 7
output:
Yes 7 5 1 0 9 11 11 9 0 20 15 0 14 1 12 12 7 0 16 1 5 6 7 0 0 5 26 0 14 16 0 1 8 5 1 8 0 18 21 0 37 0 25 0 26 0 7
result:
ok The answer is correct.
Test #83:
score: 0
Accepted
time: 47ms
memory: 4728kb
input:
49 72 72 71 33 98 98 89 89 174 174 163 163 170 170 82 98 98 202 202 179 164 282 299 299 316 316 300 262 250 250 236 154 140 148 150 150 148 148 131 95 95 106 106 108 108 81 78 78 51
output:
Yes 31 30 11 0 98 0 89 0 174 0 163 0 170 0 41 57 0 98 75 1 40 99 116 3 105 89 70 5 89 75 34 1 33 37 39 2 61 44 2 50 2 61 2 46 19 2 31 4
result:
ok The answer is correct.
Test #84:
score: 0
Accepted
time: 51ms
memory: 4476kb
input:
50 148 360 360 392 392 399 399 384 350 350 346 346 306 306 314 314 346 346 323 321 174 293 299 304 342 342 340 328 328 227 227 192 330 339 339 318 327 327 326 266 266 182 204 204 67 67 79 79 85 85
output:
Yes 74 286 0 392 0 207 192 0 350 0 346 0 306 0 314 0 131 108 107 0 21 38 39 40 60 58 40 64 3 200 0 64 133 142 0 106 111 110 0 266 0 91 113 0 67 0 79 0 85
result:
ok The answer is correct.
Test #85:
score: 0
Accepted
time: 40ms
memory: 4700kb
input:
48 200 224 224 200 267 267 259 231 246 246 215 215 196 184 180 180 270 270 270 234 230 233 233 186 114 165 165 160 190 212 212 243 243 239 239 143 143 162 162 262 264 264 246 234 238 238 22 22
output:
Yes 100 124 0 31 67 59 32 45 60 1 74 55 49 3 137 3 81 81 63 5 69 72 47 0 57 108 0 32 47 69 32 115 0 239 0 143 0 162 0 90 92 82 0 117 121 0 22
result:
ok The answer is correct.
Test #86:
score: 0
Accepted
time: 43ms
memory: 4456kb
input:
49 226 226 216 196 196 158 193 253 253 257 257 257 201 300 300 320 384 392 392 385 385 263 291 291 269 287 287 277 277 487 487 497 497 496 482 507 511 511 503 331 152 173 189 214 214 232 232 221 191
output:
Yes 118 108 0 196 0 14 21 36 36 38 38 2 56 155 3 78 110 118 3 209 87 2 182 3 75 93 4 154 4 346 6 110 109 30 66 75 79 73 29 3 8 11 19 44 11 43 32 17
result:
ok The answer is correct.
Test #87:
score: 0
Accepted
time: 47ms
memory: 4456kb
input:
49 247 247 231 383 383 381 379 398 398 397 391 195 200 227 227 197 197 339 339 337 344 344 379 388 388 379 343 405 405 412 412 402 402 412 412 398 398 415 430 430 382 382 384 384 341 198 122 124 124
output:
Yes 247 0 77 154 152 0 85 93 92 89 39 0 100 127 0 197 0 339 0 155 162 1 110 119 110 2 146 208 2 359 2 349 2 359 2 345 2 124 139 19 196 19 130 87 18 7 13 15
result:
ok The answer is correct.
Test #88:
score: 0
Accepted
time: 43ms
memory: 4440kb
input:
48 196 196 284 284 280 280 263 303 387 387 388 388 343 321 321 328 328 283 283 151 157 157 164 164 198 203 203 172 166 178 259 280 294 294 288 243 239 239 235 226 226 330 333 333 302 287 295 295
output:
Yes 196 0 284 0 280 0 75 95 179 1 197 152 1 281 1 288 1 243 1 56 62 1 124 1 51 56 38 2 8 10 27 34 44 38 23 7 49 45 7 74 7 58 61 44 39 7 143
result:
ok The answer is correct.
Test #89:
score: 0
Accepted
time: 44ms
memory: 4264kb
input:
48 244 256 256 248 253 253 269 269 250 229 229 67 252 322 261 116 372 271 372 322 333 333 393 429 429 428 347 319 294 387 234 352 370 370 317 37 193 398 10 76 215 222 222 208 344 145 171 87
output:
No
result:
ok The answer is correct.
Test #90:
score: 0
Accepted
time: 51ms
memory: 4400kb
input:
50 34 15 33 66 66 66 33 39 9 35 55 29 34 35 51 13 50 50 56 48 44 43 57 57 57 25 50 50 27 27 21 47 35 50 50 55 55 53 7 43 37 55 55 62 62 62 52 21 26 26
output:
No
result:
ok The answer is correct.
Test #91:
score: 0
Accepted
time: 57ms
memory: 4564kb
input:
49 47 64 64 64 59 74 74 3 72 19 67 71 25 61 61 58 50 49 49 58 62 70 70 69 51 70 62 62 62 62 62 54 8 41 41 41 19 40 40 20 8 24 24 20 16 16 16 19 19
output:
No
result:
ok The answer is correct.
Test #92:
score: 0
Accepted
time: 44ms
memory: 4660kb
input:
48 13 13 10 27 27 28 28 18 29 29 26 24 31 31 30 26 12 12 0 0 0 42 42 38 38 38 37 37 27 27 26 60 60 68 70 70 67 67 70 70 67 67 48 49 49 47 47 44
output:
Yes 13 0 5 22 0 19 9 0 12 9 8 0 11 10 8 1 8 0 0 0 0 42 0 19 19 0 37 0 27 0 13 47 0 34 36 0 67 0 70 0 67 0 24 25 0 25 22
result:
ok The answer is correct.
Test #93:
score: 0
Accepted
time: 53ms
memory: 4308kb
input:
50 22 22 14 24 27 27 25 25 10 47 47 45 41 42 42 44 44 43 43 0 32 32 30 27 27 10 10 14 14 14 4 11 11 9 23 23 20 28 28 22 29 31 1 28 30 30 30 30 27 27
output:
No
result:
ok The answer is correct.
Test #94:
score: 0
Accepted
time: 47ms
memory: 4392kb
input:
49 45 69 69 73 73 73 69 69 34 34 31 47 51 54 54 58 58 56 56 53 42 42 10 10 4 7 7 60 61 61 63 63 64 66 66 62 34 49 49 49 46 40 38 43 43 13 13 10 10
output:
No
result:
ok The answer is correct.
Test #95:
score: 0
Accepted
time: 43ms
memory: 4316kb
input:
48 17 17 16 16 0 27 29 32 32 36 36 39 39 35 33 21 23 23 46 46 46 46 38 38 36 36 34 34 31 33 33 36 36 30 30 28 28 23 19 19 33 37 37 15 38 39 39 0
output:
No
result:
ok The answer is correct.
Test #96:
score: 0
Accepted
time: 47ms
memory: 4348kb
input:
49 18 25 25 24 30 31 31 32 32 31 27 43 43 48 48 53 53 51 39 48 48 47 47 11 11 53 28 24 24 23 21 24 24 24 24 19 38 39 39 38 38 39 42 42 41 36 39 39 37
output:
No
result:
ok The answer is correct.
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%