QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412723 | #8225. 最小值之和 | do_while_true | 0 | 2ms | 8948kb | C++20 | 3.6kb | 2024-05-16 18:34:30 | 2024-05-16 18:34:31 |
answer
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<array>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
int cmax(int &x,int y){
if(x<y){
x=y;
return 1;
}
return 0;
}
template<typename T>
T &read(T &r){
r=0;bool w=0;char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int mod=998244353;
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
int qpow(int x,int y){
int s=1;
while(y){
if(y&1)s=1ll*s*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return s;
}
const int N=81;
int n;
int a[N],b[N];
int f[N][N][N];
int pos[N][N][N],val[N][N][N];
int solve(int i,int j,int len1,int len2,int o){
for(int w=0;w<o;w++)
if(w%len1==i&&w%len2==j)
return w;
return 0x7fffffff;
}
void dfs(int l,int r,int k,int h){
// DE("%d %d %d",l,r,k);
if(l+1==r){
b[l]=a[l]-k+h;
return ;
}
if(pos[l][r][k%(r-l)]==l){
b[l]=(a[l]-k)/(r-l)+h;
dfs(l+1,r,k+(b[l]-h)*(r-l),b[l]);
return ;
}
if(pos[l][r][k%(r-l)]==r){
b[r]=(a[r]-k)/(r-l)+h;
dfs(l,r-1,k+(b[r]-h)*(r-l),b[r]);
return ;
}
int mid=pos[l][r][k%(r-l)];
b[mid]=(f[l][r][k%(r-l)]-k)/(r-l)+h;
dfs(l,mid,k+(b[mid]-h)*(r-l),b[mid]);
dfs(mid+1,r,k+(b[mid]-h)*(r-l),b[mid]);
}
signed main(){
#ifdef do_while_true
// assert(freopen("data.in","r",stdin));
// assert(freopen("data.out","w",stdout));
#endif
read(n);
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<n;i++){
if(a[i]==a[i+1])f[i][i+1][0]=a[i];
}
for(int len=3;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=l;k<=r;k++){
if(k==l){
if(f[l+1][r][a[l]%(r-l-1)]>=a[l]){
if(cmax(f[l][r][a[l]%(r-l)],a[l])){
pos[l][r][a[l]%(r-l)]=l;
}
}
}
else if(k==r){
if(f[l][r-1][a[r]%(r-l-1)]>=a[r])
if(cmax(f[l][r][a[r]%(r-l)],a[r])){
pos[l][r][a[r]%(r-l)]=r;
}
}
else{
int len1=k-l,len2=r-(k+1);
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++){
int o=lcm(len1,len2);
int t=solve(i,j,len1,len2,o);
int up=min(f[l][k][i],f[k+1][r][j]);
if(t<=up){
t+=(up-t)/o*o;
for(int p=0;p*o<=t;p++)
if(cmax(f[l][r][(t-p*o)%(r-l)],t-p*o)){
pos[l][r][(t-p*o)%(r-l)]=k;
}
}
}
}
}
}
}
if(f[1][n][0]==-1)puts("No");
else{
puts("Yes");
dfs(1,n,0,0);
for(int i=1;i<n;i++)cout<<b[i]<<' ';
puts("");
}
#ifdef do_while_true
// cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
#endif
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: 0ms
memory: 8948kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: -11
Wrong Answer
time: 2ms
memory: 8940kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 0
result:
wrong answer Your answer is wrong.
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%