QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #303263 | #5210. Lisa's Sequences | LaStataleBlue# | WA | 0ms | 3808kb | C++23 | 2.0kb | 2024-01-12 00:08:57 | 2024-01-12 00:08:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,k;
cin>>n>>k;
vector a(n,0);
for(auto &i : a)cin>>i;
int last=-1;
vector succ(n,-1);
for(int i=n-2;i>=0;i--){
if(a[i]<a[i+1])last=2;
if(a[i]>a[i+1])last=1;
succ[i]=last;
}
vector<int> ans;
int best=n+1;
auto old = a;
for(int mode=0;mode<2;mode++){
a = old;
int cont=2,res=0;
last=-1;
bool same=(a[1]==a[0]);
int t=0;
if(a[0]<a[1])last=2,t=1;
if(a[0]>a[1])last=1,t=1;
for(int i=2;i<n;i++){
if((a[i]>=a[i-1] && last==2) || (a[i]<=a[i-1] && last==1) || last==-1){
cont++;
if(cont==k){
res++;
if(same){
if(mode==0){
a[i-1]=100'000;
}else{
a[i-1]=0;
}
}
else if(last==2){
if(i+1<n && succ[i+1]==2)a[i-1]=100'000;
else a[i]=0;
}else{
if(i+1<n && succ[i+1]==1)a[i-1]=0;
else a[i]=100'000;
}
cont=2;
}
}else{
cont=i-t+1;
}
if(a[i]!=a[i-1])same=false;
if(a[i]>a[i-1])last=2,t=i;
if(a[i]<a[i-1])last=1,t=i;
}
if(res<best){
best=res;
ans=a;
}
}
cout<<best<<"\n";
for(auto i : ans)cout<<i<<" ";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
5 3 1 2 3 4 5
output:
2 1 100000 3 4 0
result:
ok 2
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
6 3 1 1 1 1 1 1
output:
3 1 100000 1 100000 1 100000
result:
ok 3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
6 4 1 1 4 4 1 1
output:
1 1 1 4 0 1 1
result:
ok 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
6 4 4 4 4 2 2 2
output:
2 4 4 100000 2 2 100000
result:
ok 2
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 0ms
memory: 3568kb
input:
8 4 2 1 1 3 3 1 1 2
output:
2 2 1 1 100000 3 1 100000 2
result:
ok 2
Test #7:
score: 0
Accepted
time: 0ms
memory: 3628kb
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: 0ms
memory: 3536kb
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: 0ms
memory: 3496kb
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: 0ms
memory: 3548kb
input:
3 3 1 2 1
output:
0 1 2 1
result:
ok 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 3 2 1 1
output:
1 2 1 100000
result:
ok 1
Test #12:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 3 1 1 2
output:
1 1 100000 2
result:
ok 1
Test #13:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
3 3 1 1 1
output:
1 1 100000 1
result:
ok 1
Test #14:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
5 3 1 1 1 1 1
output:
2 1 100000 1 100000 1
result:
ok 2
Test #15:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
6 4 5 5 5 5 5 5
output:
2 5 5 100000 5 5 100000
result:
ok 2
Test #16:
score: 0
Accepted
time: 0ms
memory: 3548kb
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: 0ms
memory: 3540kb
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: 0ms
memory: 3604kb
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: 0ms
memory: 3604kb
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: -100
Wrong Answer
time: 0ms
memory: 3544kb
input:
8 4 4 5 5 4 3 5 5 4
output:
2 4 5 5 0 3 5 0 4
result:
wrong answer Jury has better solution 1, only 2 found