Submission #909607

#TimeUsernameProblemLanguageResultExecution timeMemory
909607MilosMilutinovicRope (JOI17_rope)C++14
100 / 100
620 ms78932 KiB
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} ll readint(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,c[1000005],cnt[1000005],res[1000005],ord[1000005]; vector<int> g[1000005]; bool bl[1000005]; void solve(int x){ for(int i=1;i<=m;i++){ cnt[i]=0; g[i].clear(); ord[i]=i; bl[i]=false; } for(int i=1;i<=n;i++) cnt[c[i]]++; for(int i=1+x;i+1<=n;i+=2){ if(c[i]==c[i+1]) continue; g[c[i]].push_back(c[i+1]); g[c[i+1]].push_back(c[i]); } sort(ord+1,ord+m+1,[&](int i,int j){return cnt[i]>cnt[j];}); for(int i=1;i<=m;i++){ for(int j:g[i]) cnt[j]--,bl[j]=true; bl[i]=true; int ptr=1; while(ptr<=m&&bl[ord[ptr]]) ptr++; int mx=0; for(int j=1;j<=ptr;j++) if(ord[j]!=i) mx=max(mx,cnt[ord[j]]); res[i]=min(res[i],n-(cnt[i]+mx)); bl[i]=false; for(int j:g[i]) cnt[j]++,bl[j]=false; } } int main() { n=readint(); m=readint(); for(int i=1;i<=n;i++) c[i]=readint(); for(int i=1;i<=m;i++) res[i]=n; solve(0); solve(1); for(int i=1;i<=m;i++) printf("%d\n",res[i]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...