QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#407101 | #8225. 最小值之和 | juicy_name | 0 | 2ms | 8000kb | C++14 | 4.4kb | 2024-05-07 23:01:22 | 2024-05-07 23:01:23 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n;
int f[maxn];
int p[85][85][85];
void exgcd(int a, int b, int &x, int &y){
if(b == 0){
x = 0; y = 1; return ;
}
exgcd(b, a % b, y, x); y -= a / b * x; return ;
}
int tp[6405]; int tc[85];
int tk[85];
pair<int, int> pc[85][85][85];
bool vis[85][85];
bool vs[85];
void dfs(int l, int r){
if(vis[l][r]) return ;
vis[l][r] = 1;
if(l == r){
if(f[l] == f[l + 1]) p[l][r][0] = f[l];
return ;
}
int N = r - l + 1;
for(int i = l;i <= r;i++){
if(i == l){
dfs(i + 1, r);
if(p[i + 1][r][f[l] % (N - 1)] < f[l]) continue;
p[l][r][f[l] % N] = max(p[l][r][f[l] % N], f[l]); continue;
}
if(i == r){
dfs(l, i - 1);
if(p[l][i - 1][f[r + 1] % (N - 1)] < f[r + 1]) continue;
p[l][r][f[r + 1] % N] = max(p[l][r][f[r + 1] % N], f[r + 1]); continue;
}
dfs(l, i - 1); dfs(i + 1, r);
int L = i - l; int R = r - i;
int pg = __gcd(L, R); int pN = L * R / pg;
int tx = 0, ty = 0; exgcd(L, R, tx, ty); int pR = R / pg;
tx = (tx % pR + pR) % pR;
for(int j = 0;j < pN;j++) tp[j] = -1;
for(int j = 0;j < L;j++){
if(p[l][i - 1][j] < 0) continue;
for(int k = 0;k < R;k++){
if(p[i + 1][r][k] < 0) continue;
if(j % pg != k % pg) continue;
int px = 1ll * (k - j) * tx % pR; px = (px + pR) % pR;
int pmi = min(p[l][i - 1][j], p[i + 1][r][k]);
int pnum = L * px + j;
if(pnum > pmi) continue;
tp[pnum] = max(tp[pnum], pnum + (pmi - pnum) / pN * pN);
}
}
for(int j = 0;j < N;j++) tc[j] = -1;
for(int j = 0;j < pN;j++){
if(tp[j] == -1) continue;
tc[tp[j] % N] = max(tc[tp[j] % N], tp[j]);
}
for(int j = 0;j < N;j++){
vs[j] = 0;
// if(tc[j] >= 0) assert(tc[j] % N == j);
}
int x = (N - pN % N) % N;
for(int j = 0;j < N;j++){
if(vs[j]) continue;
int now = j;
do{
if(tc[now] - pN > tc[(now + x) % N]){
tc[(now + x) % N] = tc[now] - pN;
}
vs[now] = 1; now = (now + x) % N;
}while(now != j);
do{
if(tc[now] - pN > tc[(now + x) % N]){
tc[(now + x) % N] = tc[now] - pN;
}
now = (now + x) % N;
}while(now != j);
}
for(int j = 0;j < N;j++){
if(tc[j] > p[l][r][j]){
p[l][r][j] = tc[j]; pc[l][r][j] = make_pair(tc[j], i);
}
}
}
// cerr << l << " " << r << endl << "? ";
// for(int i = 0;i < N;i++){
// cerr << p[l][r][i] << " ";
// }
// cerr << endl;
return ;
}
int ans[maxn];
void dfsp(int l, int r, int num, int res){
// cerr << "? " << l << " " << r << " " << num << " " << res << endl;
if(l == r){
ans[l] = f[l] - num + res; return ;
}
int N = r - l + 1;
if(f[l] % N == num % N && p[l + 1][r][f[l] % (N - 1)] >= f[l]){
ans[l] = (f[l] - num) / N + res; dfsp(l + 1, r, f[l], ans[l]); return ;
}
if(f[r + 1] % N == num % N && p[l][r - 1][f[r + 1] % (N - 1)] >= f[r + 1]){
ans[r] = (f[r + 1] - num) / N + res; dfsp(l, r - 1, f[r + 1], ans[r]); return ;
}
int pos = pc[l][r][num % N].second;
// cerr << pc[l][r][num % N].first << endl;
ans[pos] = (pc[l][r][num % N].first - num) / N + res;
dfsp(l, pos - 1, pc[l][r][num % N].first, ans[pos]);
dfsp(pos + 1, r, pc[l][r][num % N].first, ans[pos]);
return ;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> f[i];
}
if(n == 1){
cout << "Yes" << endl;
cout << endl; return 0;
}
memset(p, -1, sizeof(p));
dfs(1, n - 1);
if(p[1][n - 1][0] < 0){
cout << "No" << endl; return 0;
}
dfsp(1, n - 1, 0, 0);
cout << "Yes" << '\n';
for(int i = 1;i < n;i++){
cout << ans[i] << " ";
}
cout << '\n';
cout.flush(); 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: 6336kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: 11
Accepted
time: 0ms
memory: 6688kb
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: 7672kb
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: 0ms
memory: 6024kb
input:
5 11 11 10 5 5
output:
Yes 5 4 1 2
result:
ok The answer is correct.
Test #5:
score: 11
Accepted
time: 1ms
memory: 6124kb
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: 7932kb
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: 7952kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 11
Accepted
time: 1ms
memory: 7620kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 11
Accepted
time: 1ms
memory: 7956kb
input:
5 10 10 8 5 5
output:
Yes 5 3 1 2
result:
ok The answer is correct.
Test #10:
score: 11
Accepted
time: 1ms
memory: 7296kb
input:
5 24 24 28 28 26
output:
Yes 6 6 9 7
result:
ok The answer is correct.
Test #11:
score: 11
Accepted
time: 1ms
memory: 6896kb
input:
5 5 5 22 31 31
output:
Yes 2 1 10 19
result:
ok The answer is correct.
Test #12:
score: 11
Accepted
time: 2ms
memory: 7156kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 11
Accepted
time: 1ms
memory: 6152kb
input:
5 16 16 4 12 12
output:
Yes 13 1 1 9
result:
ok The answer is correct.
Test #14:
score: 11
Accepted
time: 1ms
memory: 7736kb
input:
5 29 29 24 26 26
output:
Yes 11 6 6 8
result:
ok The answer is correct.
Test #15:
score: 11
Accepted
time: 1ms
memory: 7668kb
input:
5 0 33 33 32 32
output:
Yes 0 13 10 12
result:
ok The answer is correct.
Test #16:
score: 11
Accepted
time: 0ms
memory: 6824kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 11
Accepted
time: 0ms
memory: 7784kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 11
Accepted
time: 1ms
memory: 7704kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 11
Accepted
time: 0ms
memory: 6212kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 11
Accepted
time: 1ms
memory: 7636kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 11
Accepted
time: 1ms
memory: 6164kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 11
Accepted
time: 0ms
memory: 6156kb
input:
5 6 7 7 6 6
output:
Yes 2 3 1 3
result:
ok The answer is correct.
Test #23:
score: 11
Accepted
time: 1ms
memory: 7824kb
input:
5 25 25 24 20 20
output:
Yes 8 7 5 5
result:
ok The answer is correct.
Test #24:
score: 11
Accepted
time: 1ms
memory: 7792kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 11
Accepted
time: 0ms
memory: 6708kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 11
Accepted
time: 0ms
memory: 7760kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 11
Accepted
time: 1ms
memory: 7668kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 11
Accepted
time: 0ms
memory: 7268kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 11
Accepted
time: 1ms
memory: 6620kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 11
Accepted
time: 0ms
memory: 7196kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 11
Accepted
time: 0ms
memory: 7960kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 11
Accepted
time: 1ms
memory: 8000kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 11
Accepted
time: 0ms
memory: 3524kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Wrong Answer
time: 0ms
memory: 3604kb
input:
1 233
output:
Yes
result:
wrong answer Line 1 expected
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%