이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1e6+5;
int ile[N], ilez[N], ans[N], tab[N];
//map<pair<int, int>, int> edg;
int n, m;
void solve(int b){
if(b==1)ilez[tab[0]]++;
if((n&1)!=b)ilez[tab[n-1]]++;
vector<pair<int, int> > V3;
for(int i=0; i<n-1; i++){
if((i&1)==b){
int u=tab[i], v=tab[i+1];
if(u>v)swap(u, v);
ilez[u]++;
ilez[v]++;
if(u!=v){
V3.push_back({u, v});
//edg[{u, v}]++;
//edg[{v, u}]++;
}
}
}
sort(V3.begin(), V3.end());
vector<pair<pair<int, int>, int> > edg;
for(auto i:V3){
if(!edg.size() || i!=edg.back().st)edg.push_back({i, 0});
edg.back().nd++;
}
vector<pair<int, int> > V;
for(int i=1; i<=m; i++){
V.push_back({ilez[i], i});
}
sort(V.begin(), V.end());
for(int i=1; i<=m; i++){
for(int j=V.size()-1; j>=0; j--){
int a=V[j].nd, b=i;
if(a>b)swap(a, b);
int s=lower_bound(edg.begin(), edg.end(), make_pair(make_pair(a, b), 0))-edg.begin();
if(a!=b && (s==edg.size() || edg[s].st!=make_pair(a, b))){
ans[i]=max(ans[i], ilez[a]+ilez[b]);
break;
}
}
}
for(auto i:edg){
if(i.st.st<i.st.nd){
int k=ilez[i.st.st]+ilez[i.st.nd]-i.nd;
ans[i.st.st]=max(ans[i.st.st], k);
ans[i.st.nd]=max(ans[i.st.nd], k);
}
}
edg.clear();
for(int i=1; i<=m; i++){
ilez[i]=0;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=0; i<n; i++)cin>>tab[i], ile[tab[i]]++;
for(int i=1; i<=m; i++)ans[i]=ile[i];
solve(0);
solve(1);
for(int i=1; i<=m; i++){
cout<<n-ans[i]<<"\n";
}
}
컴파일 시 표준 에러 (stderr) 메시지
rope.cpp: In function 'void solve(int)':
rope.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if(a!=b && (s==edg.size() || edg[s].st!=make_pair(a, b))){
| ~^~~~~~~~~~~~
# | 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... |