Submission #219593

#TimeUsernameProblemLanguageResultExecution timeMemory
219593thebesRope (JOI17_rope)C++14
0 / 100
59 ms94328 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native") #include <bits/stdc++.h> #define DEBUG 1 using namespace std; namespace output{ void __(short x){cout<<x;} void __(unsigned x){cout<<x;} void __(int x){cout<<x;} void __(long long x){cout<<x;} void __(unsigned long long x){cout<<x;} void __(double x){cout<<x;} void __(long double x){cout<<x;} void __(char x){cout<<x;} void __(const char*x){cout<<x;} void __(const string&x){cout<<x;} void __(bool x){cout<<(x?"true":"false");} template<class S,class T> void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");} template<class T> void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class S,class T> void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} void pr(){cout<<"\n";} template<class S,class... T> void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);} } using namespace output; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,char> pic; typedef pair<double,double> pdd; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vl; #define pb push_back #define fox(i,x,y) for(int i=(x);i<=(y);i++) #define foxr(i,x,y) for(int i=(y);i>=(x);i--) const int MN = 1e6+6; int N, M, i, j, arr[MN], cnt[MN]; map<int,int> adj[MN][2]; map<int,int> mp; inline void del(int x){ mp[x]--; if(!mp[x]) mp.erase(x); } int main(){ for(scanf("%d%d",&N,&M),i=1;i<=N;i++){ scanf("%d",&arr[i]); cnt[arr[i]]++; } for(i=1;i+1<=N;i+=2){ if(arr[i]!=arr[i+1]){ adj[arr[i]][0][arr[i+1]]++; adj[arr[i+1]][0][arr[i]]++; } } for(i=2;i+1<=N;i+=2){ if(arr[i]!=arr[i+1]){ adj[arr[i]][1][arr[i+1]]++; adj[arr[i+1]][1][arr[i]]++; } } for(i=1;i<=M;i++){ mp[N-cnt[i]]; } if(M==1){ printf("0\n"); return 0; } for(i=1;i<=M;i++){ int ans = N; for(j=0;j<2;j++){ del(N-cnt[i]); if(!mp[N-cnt[i]]) mp.erase(N-cnt[i]); for(auto v : adj[i][j]){ del(N-cnt[v.first]); mp[N-cnt[v.first]+v.second]++; } auto it = mp.begin(); ans = min(ans,it->first-cnt[i]); for(auto v : adj[i][j]){ del(N-cnt[v.first]+v.second); mp[N-cnt[v.first]]++; } mp[N-cnt[i]]++; } printf("%d\n",ans); } return 0; }

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:60:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&N,&M),i=1;i<=N;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
rope.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~
#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...