QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #80336 | #5210. Lisa's Sequences | hmya | WA | 163ms | 79172kb | C++14 | 4.9kb | 2023-02-23 14:35:37 | 2023-02-23 14:35:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct node{
int m,t,s;
bool friend operator < (const node &a,const node &b){
return a.m<b.m||
a.m==b.m&&a.t<b.t||
a.m==b.m&&a.t==b.t&&a.s<b.s;
}
}r[1000005][4];//分别代表变小下降，变大上升，不变下降和不变上升
int a[1000005];
int pre[1000005][4];
bool check(node a){
return a.t<k;
}
void print(int cur,int S){
if(cur==0)return;
print(cur-1,pre[cur][S]);
if(S>=2)printf("%d ",a[cur]);
if(S==0)printf("0 ");
if(S==1)printf("100000 ");
return;
}
int main(){
// freopen("kisara.in","r",stdin);
// freopen("kisara.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
r[i][0]=r[i][1]=r[i][2]=r[i][3]=node{100005,100005,100005};
}
// a[0]=a[1];
for(int i=1;i<=n;i++){
for(int S1=0;S1<4;S1++){
int P=a[i-1];
if(S1==0)P=0;
if(S1==1)P=100000;
for(int S2=0;S2<4;S2++){
int S=a[i];
if(S2==0)S=0;
if(S2==1)S=100000;
if(S2&1){//上升的状态，如果状态相同并且我比前面的大就直接更新，
if(S1&1){//两个都在上升，那么我可以接上
if(S>P){
node tmp=node{r[i-1][S1].m+(S2<2),r[i-1][S1].t+1,1};
if(check(tmp)){
if(tmp<r[i][S2]){
pre[i][S2]=S1;
}
r[i][S2]=min(r[i][S2],tmp);
}
}
else if(S==P){
node tmp=node{r[i-1][S1].m+(S2<2),r[i-1][S1].t+1,r[i-1][S1].s+1};
if(check(tmp)){
if(tmp<r[i][S2]){
pre[i][S2]=S1;
}
r[i][S2]=min(r[i][S2],tmp);
}
}
}//我上升，我前面的下降，我比他小，那就不更新
else{//如果他比我小，那么可以更新，相等的不能更新
if(S>P){
node tmp=node{r[i-1][S1].m+(S2<2),r[i-1][S1].s+1,1};
if(check(tmp)){
if(tmp<r[i][S2]){
pre[i][S2]=S1;
}
r[i][S2]=min(r[i][S2],tmp);
}
}
}
}
else{//下降的状态
if(!(S1&1)){//下降，同时我也在下降，那么续上
if(S<P){//下降，如果我在上升呢？考虑对于相邻两个数；来说，这没有代价
node tmp=node{r[i-1][S1].m+(S2<2),r[i-1][S1].t+1,1};
if(check(tmp)){
if(tmp<r[i][S2]){
pre[i][S2]=S1;
}
r[i][S2]=min(r[i][S2],tmp);
}
}
else if(S==P){
node tmp=node{r[i-1][S1].m+(S2<2),r[i-1][S1].t+1,r[i-1][S1].s+1};
if(check(tmp)){
if(tmp<r[i][S2]){
pre[i][S2]=S1;
}
r[i][S2]=min(r[i][S2],tmp);
}
}
}
else{
if(S<P){
node tmp=node{r[i-1][S1].m+(S2<2),r[i-1][S1].s+1,1};
if(check(tmp)){
if(tmp<r[i][S2]){
pre[i][S2]=S1;
}
r[i][S2]=min(r[i][S2],tmp);
}
}
}
}
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=0;j<4;j++){
// printf("%d %d %d %d %d\n",i,j,r[i][j].m,r[i][j].t,r[i][j].s);
// }
// }
int MIN=r[n][0].m,mini=0;
for(int i=1;i<4;i++){
if(r[n][i].m<MIN){
MIN=r[n][i].m;
mini=i;
}
}
printf("%d\n",MIN);
print(n,mini);
return 0;
}
/*
对于状态 u 和 d
考虑为什么寄了，因为我只需要精神胜利法说
相邻两个数决定关系，这样子，如果相邻两个数大
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7628kb
input:
5 3 1 2 3 4 5
output:
2 1 2 0 4 0
result:
ok 2
Test #2:
score: 0
Accepted
time: 3ms
memory: 7740kb
input:
6 3 1 1 1 1 1 1
output:
3 1 0 1 0 1 0
result:
ok 3
Test #3:
score: 0
Accepted
time: 1ms
memory: 7564kb
input:
6 4 1 1 4 4 1 1
output:
1 1 1 0 4 1 1
result:
ok 1
Test #4:
score: 0
Accepted
time: 3ms
memory: 7556kb
input:
6 4 4 4 4 2 2 2
output:
2 4 4 0 2 2 0
result:
ok 2
Test #5:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
6 4 4 4 4 3 4 4
output:
1 4 4 100000 3 4 4
result:
ok 1
Test #6:
score: 0
Accepted
time: 3ms
memory: 7780kb
input:
8 4 2 1 1 3 3 1 1 2
output:
2 2 1 1 3 0 1 1 0
result:
ok 2
Test #7:
score: 0
Accepted
time: 4ms
memory: 7568kb
input:
10 4 1 1 1 2 2 1 1 2 2 1
output:
2 1 1 100000 2 2 100000 1 2 2 1
result:
ok 2
Test #8:
score: 0
Accepted
time: 3ms
memory: 7780kb
input:
7 5 5 4 4 3 4 4 4
output:
0 5 4 4 3 4 4 4
result:
ok 0
Test #9:
score: 0
Accepted
time: 3ms
memory: 7552kb
input:
10 10 1 1 1 1 1 1 1 1 1 1
output:
1 1 1 1 1 1 1 1 1 100000 1
result:
ok 1
Test #10:
score: 0
Accepted
time: 3ms
memory: 7780kb
input:
3 3 1 2 1
output:
0 1 2 1
result:
ok 0
Test #11:
score: 0
Accepted
time: 3ms
memory: 7552kb
input:
3 3 2 1 1
output:
1 2 1 100000
result:
ok 1
Test #12:
score: 0
Accepted
time: 1ms
memory: 7540kb
input:
3 3 1 1 2
output:
1 1 100000 2
result:
ok 1
Test #13:
score: 0
Accepted
time: 3ms
memory: 7576kb
input:
3 3 1 1 1
output:
1 1 100000 1
result:
ok 1
Test #14:
score: 0
Accepted
time: 3ms
memory: 7552kb
input:
5 3 1 1 1 1 1
output:
2 1 100000 1 100000 1
result:
ok 2
Test #15:
score: 0
Accepted
time: 2ms
memory: 7536kb
input:
6 4 5 5 5 5 5 5
output:
2 5 5 0 5 5 0
result:
ok 2
Test #16:
score: 0
Accepted
time: 3ms
memory: 7628kb
input:
6 4 4 4 4 2 2 4
output:
1 4 4 100000 2 2 4
result:
ok 1
Test #17:
score: 0
Accepted
time: 3ms
memory: 7560kb
input:
6 4 5 5 5 5 4 2
output:
1 5 5 0 5 4 2
result:
ok 1
Test #18:
score: 0
Accepted
time: 3ms
memory: 7780kb
input:
6 4 3 3 3 2 2 3
output:
1 3 3 100000 2 2 3
result:
ok 1
Test #19:
score: 0
Accepted
time: 2ms
memory: 7552kb
input:
8 4 4 2 2 4 4 1 2 4
output:
1 4 2 2 100000 4 1 2 4
result:
ok 1
Test #20:
score: 0
Accepted
time: 3ms
memory: 7744kb
input:
8 4 4 5 5 4 3 5 5 4
output:
1 4 5 0 4 3 5 5 4
result:
ok 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 7740kb
input:
6 4 1 3 4 4 4 4
output:
1 1 3 4 0 4 4
result:
ok 1
Test #22:
score: 0
Accepted
time: 3ms
memory: 7772kb
input:
20 4 2 4 2 3 4 4 3 2 3 3 3 2 1 3 4 5 2 2 4 5
output:
4 2 4 2 3 4 0 3 2 3 3 0 2 1 3 0 5 2 2 4 0
result:
ok 4
Test #23:
score: 0
Accepted
time: 0ms
memory: 7748kb
input:
9 4 5 5 5 3 3 3 2 2 2
output:
3 5 5 0 3 3 0 2 2 0
result:
ok 3
Test #24:
score: 0
Accepted
time: 3ms
memory: 7568kb
input:
13 3 2 3 1 3 1 3 3 1 3 1 3 1 2
output:
3 2 0 1 0 1 0 3 1 3 1 3 1 2
result:
ok 3
Test #25:
score: 0
Accepted
time: 0ms
memory: 7544kb
input:
10 3 2 1 1 2 2 1 2 2 1 2
output:
3 2 100000 1 2 0 1 0 2 1 2
result:
ok 3
Test #26:
score: 0
Accepted
time: 2ms
memory: 7552kb
input:
10 3 2 3 3 2 1 1 3 1 3 1
output:
2 2 0 3 2 100000 1 3 1 3 1
result:
ok 2
Test #27:
score: 0
Accepted
time: 3ms
memory: 7564kb
input:
10 3 1 5 1 3 1 3 4 1 2 5
output:
2 1 5 1 3 1 3 0 1 0 5
result:
ok 2
Test #28:
score: 0
Accepted
time: 0ms
memory: 7628kb
input:
10 3 45193 6340 72389 96197 51013 36684 59421 49197 79404 86162
output:
2 45193 6340 72389 0 51013 36684 59421 49197 79404 0
result:
ok 2
Test #29:
score: 0
Accepted
time: 3ms
memory: 7580kb
input:
10 4 1 2 1 2 2 2 1 1 1 2
output:
2 1 2 1 2 0 2 1 1 100000 2
result:
ok 2
Test #30:
score: 0
Accepted
time: 2ms
memory: 7780kb
input:
10 4 2 3 3 1 1 2 1 2 3 3
output:
2 2 3 3 0 1 2 1 2 3 0
result:
ok 2
Test #31:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
10 4 1 1 4 3 4 5 3 4 2 5
output:
0 1 1 4 3 4 5 3 4 2 5
result:
ok 0
Test #32:
score: 0
Accepted
time: 0ms
memory: 7744kb
input:
10 4 45758 16873 75040 42225 77839 62718 13983 70028 26023 91322
output:
0 45758 16873 75040 42225 77839 62718 13983 70028 26023 91322
result:
ok 0
Test #33:
score: 0
Accepted
time: 1ms
memory: 7612kb
input:
10 5 1 2 2 1 1 2 1 2 2 1
output:
0 1 2 2 1 1 2 1 2 2 1
result:
ok 0
Test #34:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
10 5 1 1 2 2 3 2 2 1 1 1
output:
2 1 1 2 2 0 2 2 1 1 100000
result:
ok 2
Test #35:
score: 0
Accepted
time: 3ms
memory: 7504kb
input:
10 5 4 1 3 1 3 3 4 4 4 5
output:
1 4 1 3 1 3 3 100000 4 4 5
result:
ok 1
Test #36:
score: 0
Accepted
time: 4ms
memory: 7540kb
input:
10 5 55540 7942 77691 78007 13884 79534 67516 89829 81858 96483
output:
0 55540 7942 77691 78007 13884 79534 67516 89829 81858 96483
result:
ok 0
Test #37:
score: 0
Accepted
time: 2ms
memory: 7536kb
input:
10 6 2 2 2 1 2 1 2 2 2 1
output:
0 2 2 2 1 2 1 2 2 2 1
result:
ok 0
Test #38:
score: 0
Accepted
time: 3ms
memory: 7776kb
input:
10 6 1 2 3 1 3 1 3 3 1 2
output:
0 1 2 3 1 3 1 3 3 1 2
result:
ok 0
Test #39:
score: 0
Accepted
time: 4ms
memory: 7776kb
input:
10 6 3 3 3 2 1 1 5 3 5 5
output:
1 3 3 3 2 100000 1 5 3 5 5
result:
ok 1
Test #40:
score: 0
Accepted
time: 3ms
memory: 7536kb
input:
10 6 56105 97981 59850 34282 30465 96350 22078 9631 28477 1644
output:
0 56105 97981 59850 34282 30465 96350 22078 9631 28477 1644
result:
ok 0
Test #41:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
10 7 1 2 2 2 1 2 1 1 1 1
output:
0 1 2 2 2 1 2 1 1 1 1
result:
ok 0
Test #42:
score: 0
Accepted
time: 3ms
memory: 7772kb
input:
10 7 1 3 2 2 1 2 3 2 1 1
output:
0 1 3 2 2 1 2 3 2 1 1
result:
ok 0
Test #43:
score: 0
Accepted
time: 0ms
memory: 7604kb
input:
10 7 3 4 4 5 4 3 4 3 3 5
output:
0 3 4 4 5 4 3 4 3 3 5
result:
ok 0
Test #44:
score: 0
Accepted
time: 1ms
memory: 7780kb
input:
10 7 56671 99297 62500 89526 57292 22385 76640 20216 84312 6804
output:
0 56671 99297 62500 89526 57292 22385 76640 20216 84312 6804
result:
ok 0
Test #45:
score: 0
Accepted
time: 2ms
memory: 7536kb
input:
10 8 2 1 2 2 2 2 1 2 2 2
output:
0 2 1 2 2 2 2 1 2 2 2
result:
ok 0
Test #46:
score: 0
Accepted
time: 3ms
memory: 7564kb
input:
10 8 1 3 3 3 3 1 2 3 2 1
output:
0 1 3 3 3 3 1 2 3 2 1
result:
ok 0
Test #47:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
10 8 4 5 2 2 2 4 5 1 4 3
output:
0 4 5 2 2 2 4 5 1 4 3
result:
ok 0
Test #48:
score: 0
Accepted
time: 3ms
memory: 7532kb
input:
10 8 36744 99583 65151 35555 93335 39201 31202 50263 30931 21182
output:
0 36744 99583 65151 35555 93335 39201 31202 50263 30931 21182
result:
ok 0
Test #49:
score: 0
Accepted
time: 3ms
memory: 7560kb
input:
10 9 2 1 1 2 2 1 2 2 2 2
output:
0 2 1 1 2 2 1 2 2 2 2
result:
ok 0
Test #50:
score: 0
Accepted
time: 3ms
memory: 7552kb
input:
10 9 3 3 3 1 2 2 2 3 2 2
output:
0 3 3 3 1 2 2 2 3 2 2
result:
ok 0
Test #51:
score: 0
Accepted
time: 0ms
memory: 7576kb
input:
10 9 2 5 2 5 5 1 3 2 5 5
output:
0 2 5 2 5 5 1 3 2 5 5
result:
ok 0
Test #52:
score: 0
Accepted
time: 2ms
memory: 7536kb
input:
10 9 46526 90653 57556 81583 9917 65235 75517 70064 77549 26342
output:
0 46526 90653 57556 81583 9917 65235 75517 70064 77549 26342
result:
ok 0
Test #53:
score: 0
Accepted
time: 1ms
memory: 7564kb
input:
10 10 1 2 2 2 2 1 1 2 1 1
output:
0 1 2 2 2 2 1 1 2 1 1
result:
ok 0
Test #54:
score: 0
Accepted
time: 3ms
memory: 7748kb
input:
10 10 3 1 2 1 2 3 1 3 1 1
output:
0 3 1 2 1 2 3 1 3 1 1
result:
ok 0
Test #55:
score: 0
Accepted
time: 1ms
memory: 7564kb
input:
10 10 1 4 4 5 4 2 3 2 2 2
output:
0 1 4 4 5 4 2 3 2 2 2
result:
ok 0
Test #56:
score: 0
Accepted
time: 3ms
memory: 7536kb
input:
10 10 7713 90031 59708 15268 29396 79470 40228 76226 57485 12718
output:
0 7713 90031 59708 15268 29396 79470 40228 76226 57485 12718
result:
ok 0
Test #57:
score: 0
Accepted
time: 2ms
memory: 7612kb
input:
30 3 1 1 2 2 1 1 1 2 2 2 2 1 2 1 2 1 1 2 1 2 2 2 2 2 1 2 1 2 1 1
output:
11 1 100000 2 100000 1 100000 1 2 0 2 0 1 0 1 0 1 0 2 1 2 0 2 0 2 1 2 1 2 1 100000
result:
ok 11
Test #58:
score: 0
Accepted
time: 2ms
memory: 7520kb
input:
30 3 1 3 2 3 1 2 1 1 1 2 3 2 3 3 1 1 2 2 2 1 3 3 1 3 3 2 1 1 1 3
output:
9 1 3 2 3 1 2 1 100000 1 2 0 2 0 3 1 100000 2 100000 2 100000 3 100000 1 3 0 2 1 100000 1 3
result:
ok 9
Test #59:
score: 0
Accepted
time: 3ms
memory: 7616kb
input:
30 3 1 2 1 5 1 3 3 2 2 4 1 2 5 4 3 5 2 2 3 4 2 5 2 3 1 3 2 5 2 1
output:
5 1 2 1 5 1 3 0 2 0 4 1 2 0 4 3 5 2 100000 3 4 2 5 2 3 1 3 2 5 2 100000
result:
ok 5
Test #60:
score: 0
Accepted
time: 3ms
memory: 7508kb
input:
30 3 46794 11642 64446 48822 93862 35562 9271 42435 89725 22019 95837 29908 59376 24224 24200 55981 88803 56777 85133 10604 67092 52105 17027 3049 98119 19228 1570 2996 16069 44400
output:
5 46794 11642 64446 48822 93862 35562 100000 42435 89725 22019 95837 29908 59376 24224 100000 55981 88803 56777 85133 10604 67092 52105 100000 3049 98119 19228 100000 2996 16069 0
result:
ok 5
Test #61:
score: 0
Accepted
time: 3ms
memory: 7776kb
input:
30 4 2 1 2 2 2 1 1 2 1 1 1 1 1 2 1 1 1 1 2 2 1 1 2 1 2 2 1 1 2 2
output:
5 2 1 2 0 2 1 1 2 1 1 100000 1 1 2 1 1 100000 1 2 2 0 1 2 1 2 2 1 100000 2 2
result:
ok 5
Test #62:
score: 0
Accepted
time: 3ms
memory: 7564kb
input:
30 4 1 1 3 2 1 3 2 1 3 2 2 2 2 3 3 3 2 1 2 1 1 3 2 1 2 1 1 2 2 1
output:
3 1 1 3 2 1 3 2 1 3 2 2 100000 2 3 3 0 2 1 2 1 1 3 2 1 2 1 1 100000 2 1
result:
ok 3
Test #63:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
30 4 1 3 4 4 4 5 4 3 4 2 5 5 3 5 3 5 3 4 5 5 3 5 4 2 4 4 1 1 5 4
output:
3 1 3 100000 4 4 5 4 3 4 2 5 5 3 5 3 5 3 4 0 5 3 5 4 2 4 4 0 1 5 4
result:
ok 3
Test #64:
score: 0
Accepted
time: 2ms
memory: 7568kb
input:
30 4 47360 1682 67096 94850 20690 61595 63832 72482 45561 27180 8643 78413 70252 55432 95417 52362 44995 51511 99980 49672 20621 48503 60046 82179 13917 82990 50203 87463 50161 50380
output:
2 47360 1682 67096 94850 20690 61595 63832 0 45561 27180 8643 78413 70252 55432 95417 52362 44995 51511 99980 49672 20621 48503 0 82179 13917 82990 50203 87463 50161 50380
result:
ok 2
Test #65:
score: 0
Accepted
time: 0ms
memory: 7564kb
input:
30 5 1 1 2 2 1 2 2 1 1 1 2 2 2 1 1 2 1 1 2 2 1 1 2 1 2 2 2 1 2 2
output:
2 1 1 2 2 1 2 2 1 1 100000 2 2 2 100000 1 2 1 1 2 2 1 1 2 1 2 2 2 1 2 2
result:
ok 2
Test #66:
score: 0
Accepted
time: 1ms
memory: 7580kb
input:
30 5 2 3 1 3 2 3 2 2 3 3 3 2 1 2 2 1 1 3 1 3 1 2 1 2 1 1 1 1 2 1
output:
2 2 3 1 3 2 3 2 2 3 3 0 2 1 2 2 1 1 3 1 3 1 2 1 2 1 1 100000 1 2 1
result:
ok 2
Test #67:
score: 0
Accepted
time: 3ms
memory: 7772kb
input:
30 5 1 4 5 3 3 3 3 1 4 4 1 5 1 4 2 4 1 2 5 4 5 4 4 4 1 5 1 1 4 1
output:
2 1 4 5 3 3 3 100000 1 4 4 1 5 1 4 2 4 1 2 5 4 5 4 4 100000 1 5 1 1 4 1
result:
ok 2
Test #68:
score: 0
Accepted
time: 0ms
memory: 7632kb
input:
30 5 47925 92750 59501 40878 47517 78412 18394 92283 92179 41557 40911 17701 51420 96886 57419 29281 10404 47275 26104 98986 63903 43871 93847 70527 20496 47781 9084 82178 74006 36897
output:
1 47925 92750 59501 40878 47517 78412 18394 92283 92179 41557 40911 100000 51420 96886 57419 29281 10404 47275 26104 98986 63903 43871 93847 70527 20496 47781 9084 82178 74006 36897
result:
ok 1
Test #69:
score: -100
Wrong Answer
time: 163ms
memory: 79172kb
input:
1000000 3 1 2 1 2 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 1 1 1 1 2 1 1 1 1 2 2 2 1 1 2 2 1 2 2 1 2 2 2 1 1 2 1 1 2 2 2 1 1 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 1 2 2 2 2 1 1 2 1 2 1 1 2 1 2 2 1 2 1 2 1 2 1 2 2 2 2 1 1 2 2 2 2 1 2 2 1 2 2 2 2 1 2 1 2 2 2 1 2 1 2 1 1 1 2 2 2 1 2 1 2 ...
output:
100005 1 2 1 2 0 1 0 1 0 1 0 1 0 2 1 100000 1 100000 1 2 1 100000 1 2 0 1 0 1 0 1 0 2 0 1 0 1 0 1 0 1 0 1 0 1 0 2 0 2 1 100000 2 100000 1 2 0 1 0 2 0 1 0 2 1 100000 2 100000 2 100000 1 2 0 2 1 2 1 2 0 1 0 1 0 2 1 100000 1 2 0 2 0 1 0 2 1 2 1 100000 2 100000 2 100000 1 2 1 2 1 2 1 2 0 2 0 1 0 2 0 2 0...
result:
wrong answer Promised to change 100005 elements, but 849904 were changed