# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
362819 | denkendoemeer | Rope (JOI17_rope) | C++14 | 1112 ms | 80592 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int v[1000005],cost[1000005],ind[1000005];
vector<int>g[1000005];
int cmp(int a,int b)
{
return cost[a]<cost[b];
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int n,m,i;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%d",&v[i]);
v[i]--;
g[v[i]].push_back(i);
cost[v[i]]--;
}
for(i=0;i<m;i++)
ind[i]=i;
sort(ind,ind+m,cmp);
int cul;
for(cul=0;cul<m;cul++){
int ans=n-(int)g[cul].size();
for(i=0;i<2;i++){
int cnt=0;
for(auto it:g[cul]){
if (it>0 && it%2!=i){
cost[v[it-1]]++;
cnt++;
}
if (it<n-1 && (it+1)%2!=i){
cost[v[it+1]]++;
cnt++;
}
}
cnt=min(cnt+2,m);
int num=n,j;
for(j=0;j<cnt;j++){
if (ind[j]==cul)
continue;
num=min(num,cost[ind[j]]);
}
ans=min(ans,n-(int)g[cul].size()+num);
for(auto it:g[cul]){
if (it>0 && it%2!=i)
cost[v[it-1]]--;
if (it<n-1 && (it+1)%2!=i)
cost[v[it+1]]--;
}
}
printf("%d\n",ans);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |