QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#670029 | #8225. 最小值之和 | Daniel777 | 0 | 1ms | 7796kb | C++14 | 3.3kb | 2024-10-23 20:17:38 | 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%