제출 #757064

#제출 시각아이디문제언어결과실행 시간메모리
7570641binRope (JOI17_rope)C++14
100 / 100
935 ms76620 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e6 + 5; int n, m, a[NMAX], C[NMAX], cnt[NMAX], mx, ans; vector<int> v[NMAX]; void add(int c, int f){ cnt[C[c]]--; if(!f){ cnt[--C[c]]++; if(!cnt[mx]) mx--; } else{ cnt[++C[c]]++; if(cnt[mx + 1]) mx++; } return; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; cnt[0] = m; for(int i = 0; i < n; i++) { cin >> a[i]; add(a[i], 1); v[a[i]].emplace_back(i); } for(int c = 1; c <= m; c++){ for(int i = 0; i < v[c].size(); i++) add(c, 0); ans = 1e9; for(int f = 0; f < 2; f++){ int ret = n - v[c].size(); for(int& ix : v[c]){ if((ix & 1) == f){ if(ix + 1 < n && a[ix + 1] != c) add(a[ix + 1], 0); } else{ if(ix && a[ix - 1] != c) add(a[ix - 1], 0); } } ans = min(ans, ret - mx); for(int& ix : v[c]){ if((ix & 1) == f){ if(ix + 1 < n && a[ix + 1] != c) add(a[ix + 1], 1); } else{ if(ix && a[ix - 1] != c) add(a[ix - 1], 1); } } } cout << ans << '\n'; for(int i = 0; i < v[c].size(); i++) add(c, 1); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

rope.cpp: In function 'int main()':
rope.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i = 0; i < v[c].size(); i++) add(c, 0);
      |                        ~~^~~~~~~~~~~~~
rope.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i = 0; i < v[c].size(); i++) add(c, 1);
      |                        ~~^~~~~~~~~~~~~
#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...