QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326538 | #8225. 最小值之和 | linrui# | 11 | 37ms | 4436kb | C++14 | 2.9kb | 2024-02-13 13:12:18 | 2024-07-04 03:23:51 |
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,W){
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: 0ms
memory: 3816kb
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: 3800kb
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: 3800kb
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: 0ms
memory: 3840kb
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: 0ms
memory: 3756kb
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: 3812kb
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: 3808kb
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: 3812kb
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: 3876kb
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: 3872kb
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: 0ms
memory: 3812kb
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: 0ms
memory: 3780kb
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: 0ms
memory: 3804kb
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: 4072kb
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: 0ms
memory: 3812kb
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: 0ms
memory: 3608kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 0ms
memory: 3804kb
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: 3848kb
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: 3744kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 0ms
memory: 3924kb
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: 3656kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Accepted
time: 0ms
memory: 3564kb
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: 4104kb
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: 1ms
memory: 3776kb
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: 3836kb
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: 1ms
memory: 3912kb
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: 0ms
memory: 3828kb
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: 3676kb
input:
8 1313 1695 1695 1129 1129 711 557 557
output:
No
result:
wrong answer Line 1 expected P7
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #77:
score: 25
Accepted
time: 37ms
memory: 4432kb
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: -25
Wrong Answer
time: 36ms
memory: 4436kb
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 0 0 21 25 0 20 40 0 0 0 0 0 4 2
result:
wrong answer Your answer is wrong.
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%