QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#670029#8225. 最小值之和Daniel7770 1ms7796kbC++143.3kb2024-10-23 20:17:382024-10-23 20:17:38

Judging History

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

  • [2024-10-23 20:17:38]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7796kb
  • [2024-10-23 20:17:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(a == 0) return x = 0,y = 1,b;
    ll g = exgcd(b%a,a,y,x);
    x -= b/a*y;
    return g;
}
ll f[85][85][85],pos[85][85][85];
int n;
ll a[85],b[85];
ll res[85];
priority_queue<int>q;
void print(int l,int r,int x)
{
    if(l > r) return ;
    int sz = r-l+1,mid = pos[l][r][x%sz];
    //if(mid > r || mid < l) assert(0);
    for(int i = l;i <= r;i++) b[i] += (f[l][r][x%sz]-x)/sz;
    x = f[l][r][x%sz];
    print(l,mid-1,x);
    cout<<b[mid]<<" ";
    print(mid+1,r,x);
}
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>a[i];
    for(int l = n-1;l;l--)
    {
        f[l][l][0] = a[l]==a[l+1]?a[l]:-1;
        pos[l][l][0] = l;
        for(int r = l+1;r < n;r++)
        {
            int sz = r-l+1;
            for(int i = 0;i < sz;i++)
            {
                f[l][r][i] = -1;
            }
            if(f[l+1][r][a[l]%(sz-1)] >= a[l])
            {
                f[l][r][a[l]%sz] = max(f[l][r][a[l]%sz],a[l]);
                pos[l][r][a[l]%sz] = l;
            }
            if(f[l][r-1][a[r+1]%(sz-1)] >= a[r+1])
            {
                f[l][r][a[r+1]%sz] = max(f[l][r][a[r+1]%sz],a[r+1]);
                if(f[l][r][a[r+1]%sz] == a[r+1]) pos[l][r][a[r+1]%sz] = r;
            }
            for(int mid = l+1;mid < r;mid++)
            {
                ll X = 0,Y = 0;
                int lsz = mid-l,rsz = r-mid,g = exgcd(lsz+1,rsz+1,X,Y);
                ll P = (lsz+1)*(rsz+1)/g;
                memset(res,-1,sizeof(res));
                for(int x = 0;x < lsz;x++)
                {
                    for(int y = 0;y < rsz;y++)
                    {
                        ll fl = f[l][mid-1][x],fr = f[mid+1][r][y];
                        //这里fl-(rsz+1)*x = fr-(lsz+1)*y
                        //(rsz+1)*x - (lst+1)*y = fl-fr
                        if(fl == -1 || fr == -1) continue;
                        if((fr-fl)%g) continue;
                        ll nx = X * (fl-fr)/g;
                        ll val = fl - (rsz+1)*nx;
                        fl = min(fl,fr);
                        if(val < fl) val += (fl-val)/P*P;
                        else val -= (val-fl-1+P)/P*P;
                        if(val >= 0) q.push(val);
                        //if(l == 1 && r == 4 && mid == 2 && x == 0 && y == 0)
                        //{
                        //    cout<<"!"<<val<<"\n";
                        //}
                    }
                }
                while(!q.empty())
                {
                    auto tp = q.top();q.pop();
                    if(res[tp%sz] >= 0) continue;
                    res[tp%sz] = tp;
                    if(tp >= P) tp -= P,q.push(tp); 
                }
                for(int i = 0;i < sz;i++)
                {
                    if(res[i] > f[l][r][i])
                    {
                        f[l][r][i] = res[i];
                        pos[l][r][i] = mid;
                    }
                }
            }
        }
    }
    if(f[1][n-1][0] == -1)
    {
        cout<<"No\n";
        return 0;
    }
    cout<<"Yes\n";
    //cout<<pos[1][2][0]<<"\n";
    print(1,n-1,0);
    cout<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 11
Accepted
time: 1ms
memory: 5636kb

input:

5
14 14 12 13 13

output:

Yes
8 2 4 5 

result:

ok The answer is correct.

Test #2:

score: 11
Accepted
time: 1ms
memory: 5688kb

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1 

result:

ok The answer is correct.

Test #3:

score: 11
Accepted
time: 1ms
memory: 5632kb

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4 

result:

ok The answer is correct.

Test #4:

score: 11
Accepted
time: 1ms
memory: 7796kb

input:

5
11 11 10 5 5

output:

Yes
6 5 0 5 

result:

ok The answer is correct.

Test #5:

score: 11
Accepted
time: 1ms
memory: 5612kb

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1 

result:

ok The answer is correct.

Test #6:

score: 11
Accepted
time: 1ms
memory: 5744kb

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1 

result:

ok The answer is correct.

Test #7:

score: 11
Accepted
time: 1ms
memory: 5636kb

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8 

result:

ok The answer is correct.

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 5688kb

input:

5
2 2 6 11 11

output:

No

result:

wrong answer Line 1 expected \x10

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%