Submission #241658

#TimeUsernameProblemLanguageResultExecution timeMemory
241658arnold518Rope (JOI17_rope)C++14
100 / 100
1441 ms84732 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e6; int N, M, A[MAXN+10]; int val[MAXN+10], cnt[MAXN+10], maxv=0, ans[MAXN+10]; vector<int> V[MAXN+10]; void init() { int i, j; memset(val, 0, sizeof(val)); memset(cnt, 0, sizeof(cnt)); for(i=1; i<=M; i++) V[i].clear(); maxv=0; val[0]=N; } void push(int x) { val[cnt[x]]--; cnt[x]++; val[cnt[x]]++; maxv=max(maxv, cnt[x]); } void pop(int x) { val[cnt[x]]--; if(val[maxv]==0) maxv--; cnt[x]--; val[cnt[x]]++; } int main() { int i, j; scanf("%d%d", &N, &M); for(i=1; i<=N; i++) scanf("%d", &A[i]); for(i=1; i<=M; i++) ans[i]=987654321; init(); for(i=1; i<=N; i++) push(A[i]); for(i=1; i<=N; i+=2) { int a, b; if(i+1<=N) { a=A[i], b=A[i+1]; if(a==b) continue; V[a].push_back(b); V[b].push_back(a); } } for(i=1; i<=M; i++) { int t=cnt[i]; for(j=1; j<=t; j++) pop(i); for(auto it : V[i]) pop(it); ans[i]=min(ans[i], N-t-maxv); for(auto it : V[i]) push(it); for(j=1; j<=t; j++) push(i); } init(); for(i=1; i<=N; i++) push(A[i]); for(i=2; i<=N; i+=2) { int a, b; if(i+1<=N) { a=A[i], b=A[i+1]; if(a==b) continue; V[a].push_back(b); V[b].push_back(a); } } for(i=1; i<=M; i++) { int t=cnt[i]; for(j=1; j<=t; j++) pop(i); for(auto it : V[i]) pop(it); ans[i]=min(ans[i], N-t-maxv); for(auto it : V[i]) push(it); for(j=1; j<=t; j++) push(i); } for(i=1; i<=M; i++) printf("%d\n", ans[i]); }

Compilation message (stderr)

rope.cpp: In function 'void init()':
rope.cpp:16:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
rope.cpp: In function 'int main()':
rope.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
rope.cpp:45:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[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...