제출 #824676

#제출 시각아이디문제언어결과실행 시간메모리
824676kshitij_sodaniRope (JOI17_rope)C++17
100 / 100
958 ms144352 KiB
#include <bits/stdc++.h> #define a first #define b second #define pb push_back using namespace std; #define endl '\n' typedef long long llo; int it[1000001]; int ans[1000001]; int co[1000001]; int vis[1000001]; int vis2[1000001]; vector<int> adj[1000001][2]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin>>n>>m; for(int i=0;i<m;i++){ ans[i]=n; } for(int i=0;i<n;i++){ cin>>it[i]; it[i]--; co[it[i]]++; ans[it[i]]--; } vector<pair<int,int>> xx; for(int i=0;i<m;i++){ xx.pb({co[i],i}); //xx.insert({co[i],i}); } sort(xx.begin(),xx.end()); reverse(xx.begin(),xx.end()); //map<pair<pair<int,int>,int>,int> ss; for(int i=0;i<n-1;i++){ if(it[i]!=it[i+1]){ adj[it[i]][i%2].pb(it[i+1]); adj[it[i+1]][i%2].pb(it[i]); } } for(int i=0;i<m;i++){ vector<int> ss; //xx.erase({co[i],i}); ss.pb(i); for(auto j:adj[i][0]){ if(vis[j]==0){ // xx.erase({co[j],j}); ss.pb(j); } vis[j]++; } for(auto j:adj[i][1]){ if(vis[j]==0 and vis2[j]==0){ // xx.erase({co[j],j}); ss.pb(j); } vis2[j]++; } for(auto j:xx){ if(j.b==i){ continue; } ans[i]=min(ans[i],n-co[i]-j.a+min(vis[j.b],vis2[j.b])); if(vis[j.b]==0 and vis2[j.b]==0){ break; } } for(auto j:ss){ vis[j]=0; vis2[j]=0; } } for(int i=0;i<m;i++){ cout<<ans[i]<<endl; } 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...