QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709108#8225. 最小值之和miaomiaomiaowuCompile Error//C++204.6kb2024-11-04 11:35:222024-11-04 11:35:22

Judging History

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

  • [2024-11-04 11:35:22]
  • 评测
  • [2024-11-04 11:35:22]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<ll,ll>
const double PI=acos(-1.0);
template <class Miaowu>
inline void in(Miaowu &x){
    char c;x=0;bool f=0;
    for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
struct fastmod{
    typedef unsigned long long u64;
    typedef __uint128_t u128;
    int m;u64 b;
    fastmod(int m):m(m),b(((u128)1<<64)/m){}
    int reduce(u64 a){
        u64 q=((u128)a*b)>>64;
        int r=a-q*m;
        return r<m?r:r-m;
    }
}z(2);
int n,Lx[81],Rx[81];
ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81];
struct Node{int k,l,r;ll x;}pd[81][81][81];
inline ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1,y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll x0=x,y0=y;x=y0,y=x0-a/b*y0;
    return d;
}
inline pii calc(ll t1,ll m1,ll lim1,ll t2,ll m2,ll lim2){
    if(m2<m1)swap(t1,t2),swap(m1,m2),swap(lim1,lim2);
    ll X,Y,d=exgcd(t1,t2,X,Y),xx=m2-m1;
    if(xx%d!=0)return MP(-1,-1);
    X*=xx/d,Y*=xx/d,Y=-Y;
    ll mx=0,q1=lcm[t1][t2]/t1,q2=lcm[t1][t2]/t2;
    if(X>lim1)mx=max(mx,(X-lim1-1)/q1+1);
    if(Y>lim2)mx=max(mx,(Y-lim2-1)/q2+1);
    if(mx!=0)X-=q1*mx,Y-=q2*mx;
    ll mn;
    if(X==lim1||Y==lim2)mn=0;
    else mn=min((lim1-X)/q1,(lim2-Y)/q2);
    if(mn!=0)X+=mn*q1,Y+=mn*q2;
    if(X<0||Y<0)return MP(-1,-1);
    return MP(X*t1+m1,min(X/q1,Y/q2));
}
inline void getans(int l,int r,int x,ll nw){
    if(l==r)return;
    int k=pd[l][r][x].k,xl=pd[l][r][x].l,xr=pd[l][r][x].r;
    ll num=(pd[l][r][x].x-nw)/(r-l);
    for(int i=l;i<r;i++)ans[i]+=num;
    getans(l,k,xl,pd[l][r][x].x);
    getans(k+1,r,xr,pd[l][r][x].x);
}
int main(){
    for(int i=1;i<=80;i++)for(int j=1;j<=80;j++)
        lcm[i][j]=i/__gcd(i,j)*j;
    in(n);
    memset(dp,-1,sizeof dp);
    for(int i=1;i<=n;i++)in(a[i]);
    for(int i=1;i<n;i++)if(a[i]==a[i+1])dp[i][i+1][0]=a[i],pd[i][i+1][0]=Node{i,0,0,a[i]};
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){
        mn[i][j]=a[i];
        for(int k=i+1;k<=j;k++)mn[i][j]=min(mn[i][j],a[k]);
    }
    for(int d=3;d<=n;d++){
        for(int l=1,r=d;r<=n;l++,r++){
            for(int k=l;k<r;k++){
                memset(dis,-1,sizeof dis);
                if(k==l){
                    for(int xr=0;xr<r-k-1;xr++)if(dp[k+1][r][xr]!=-1){
                        ll num=(r-k-1)*dp[k+1][r][xr]+xr;
                        if(num>=a[l]&&(num-a[l])%(r-k-1)==0){
                            int rst=a[l]%(r-l);ll qwq=a[l]/(r-l);
                            if(qwq>dp[l][r][rst])dp[l][r][rst]=qwq,pd[l][r][rst]=Node{k,0,xr,a[l]};
                        }
                    }
                    continue;
                }
                if(k==r-1){
                    for(int xl=0;xl<k-l;xl++)if(dp[l][k][xl]!=-1){
                        ll num=(k-l)*dp[l][k][xl]+xl;
                        if(num>=a[r]&&(num-a[r])%(k-l)==0){
                            int rst=a[r]%(r-l);ll qwq=a[r]/(r-l);
                            if(qwq>dp[l][r][rst])dp[l][r][rst]=qwq,pd[l][r][rst]=Node{k,xl,0,a[r]};
                        }
                    }
                    continue;
                }
                for(int xl=0;xl<k-l;xl++)if(dp[l][k][xl]!=-1){
                    for(int xr=0;xr<r-k-1;xr++)if(dp[k+1][r][xr]!=-1){
                        pii qwq=calc(k-l,xl,dp[l][k][xl],r-k-1,xr,dp[k+1][r][xr]);
                        if(qwq.first==-1)continue;
                        int t=lcm[r-k-1][k-l];
                        while(qwq.second>=0){
                            ll xx=qwq.first%(r-l),yy=qwq.first/(r-l);
                            if(yy>dis[xx])dis[xx]=yy,Lx[xx]=xl,Rx[xx]=xr;
                            qwq.second--,qwq.first-=t;
                        }
                    }
                }
                for(int i=0;i<r-l;i++)if(dis[i]!=-1){
                    if(dis[i]>dp[l][r][i]){
                        dp[l][r][i]=dis[i],pd[l][r][i]=Node{k,Lx[i],Rx[i],dis[i]*(r-l)+i};
                    }
                }
            }
        }
    }
    if(dp[1][n][0]==-1)return puts("No"),0;
    getans(1,n,0,0);
    for(int i=1;i<n;i++)for(int j=i;j<n;j++){
        mn[i][j]=ans[i];
        for(int k=i+1;k<=j;k++)mn[i][j]=min(mn[i][j],ans[k]);
    }
    for(int i=1;i<=n;i++){
        ll qwq=0;
        for(int j=1;j<i;j++)qwq+=mn[j][i-1];
        for(int j=i;j<n;j++)qwq+=mn[i][j];
        if(qwq!=a[i])return puts("No"),0;
    }
    puts("Yes");
    for(int i=1;i<n;i++)cout<<ans[i]<<' ';
    return 0;
}

Details

answer.code: In function ‘std::pair<long long int, long long int> calc(ll, ll, ll, ll, ll, ll)’:
answer.code:41:16: error: reference to ‘lcm’ is ambiguous
   41 |     ll mx=0,q1=lcm[t1][t2]/t1,q2=lcm[t1][t2]/t2;
      |                ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:58,
                 from answer.code:1:
/usr/include/c++/13/numeric:179:5: note: candidates are: ‘template<class _Mn, class _Nn> constexpr std::common_type_t<_Tp1, _Tp2> std::lcm(_Mn, _Nn)’
  179 |     lcm(_Mn __m, _Nn __n) noexcept
      |     ^~~
answer.code:28:25: note:                 ‘ll lcm [81][81]’
   28 | ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81];
      |                         ^~~
answer.code:43:36: error: ‘q2’ was not declared in this scope; did you mean ‘q1’?
   43 |     if(Y>lim2)mx=max(mx,(Y-lim2-1)/q2+1);
      |                                    ^~
      |                                    q1
answer.code:44:26: error: ‘q2’ was not declared in this scope; did you mean ‘q1’?
   44 |     if(mx!=0)X-=q1*mx,Y-=q2*mx;
      |                          ^~
      |                          q1
answer.code:47:38: error: ‘q2’ was not declared in this scope; did you mean ‘q1’?
   47 |     else mn=min((lim1-X)/q1,(lim2-Y)/q2);
      |                                      ^~
      |                                      q1
answer.code:48:29: error: ‘q2’ was not declared in this scope; did you mean ‘q1’?
   48 |     if(mn!=0)X+=mn*q1,Y+=mn*q2;
      |                             ^~
      |                             q1
answer.code:50:34: error: ‘q2’ was not declared in this scope; did you mean ‘q1’?
   50 |     return MP(X*t1+m1,min(X/q1,Y/q2));
      |                                  ^~
      |                                  q1
answer.code: In function ‘int main()’:
answer.code:62:9: error: reference to ‘lcm’ is ambiguous
   62 |         lcm[i][j]=i/__gcd(i,j)*j;
      |         ^~~
/usr/include/c++/13/numeric:179:5: note: candidates are: ‘template<class _Mn, class _Nn> constexpr std::common_type_t<_Tp1, _Tp2> std::lcm(_Mn, _Nn)’
  179 |     lcm(_Mn __m, _Nn __n) noexcept
      |     ^~~
answer.code:28:25: note:                 ‘ll lcm [81][81]’
   28 | ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81];
      |                         ^~~
answer.code:99:31: error: reference to ‘lcm’ is ambiguous
   99 |                         int t=lcm[r-k-1][k-l];
      |                               ^~~
/usr/include/c++/13/numeric:179:5: note: candidates are: ‘template<class _Mn, class _Nn> constexpr std::common_type_t<_Tp1, _Tp2> std::lcm(_Mn, _Nn)’
  179 |     lcm(_Mn __m, _Nn __n) noexcept
      |     ^~~
answer.code:28:25: note:                 ‘ll lcm [81][81]’
   28 | ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81];
      |                         ^~~