Submission #964791

#TimeUsernameProblemLanguageResultExecution timeMemory
964791efedmrlrRope (JOI17_rope)C++17
80 / 100
130 ms262144 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define lli long long int #define MP make_pair #define pb push_back #define REP(i,n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const double EPS = 0.00001; const int INF = 1e9+500; const int N = 3e5+5; const int ALPH = 26; const int LGN = 25; constexpr int MOD = 1e9+7; int n,m,q; vector<int> a; vector<int> cnt1, cnt2; vector<vector<int> > mpp1, mpp2; inline void solve() { cin>>n>>m; a.resize(n + 5); cnt1.assign(m + 5, 0); cnt2.assign(m + 5, 0); mpp1.assign(m + 5, vector<int>(m + 5, 0)); mpp2.assign(m + 5, vector<int>(m + 5, 0)); for(int i = 1; i<=n; i++) { cin >> a[i]; } for(int i = 1; i<n; i+=2) { cnt1[a[i]]++; cnt1[a[i + 1]]++; mpp1[min(a[i], a[i + 1])][max(a[i], a[i + 1])]++; } for(int i = 2; i<n; i+=2) { cnt2[a[i]]++; cnt2[a[i + 1]]++; mpp2[min(a[i], a[i + 1])][max(a[i], a[i + 1])]++; } vector<int> res(m + 1, INF); for(int i = 1; i <= m; i++) { for(int j = i + 1; j <= m; j++) { int ret = n; if((n & 1) && (a[n] == i || a[n] == j)) { ret--; } ret -= cnt1[i] + cnt1[j]; ret += mpp1[i][j]; res[i] = min(res[i], ret); res[j] = min(res[j], ret); ret = n; if(!(n & 1) && (a[n] == i || a[n] == j)) { ret--; } if(a[1] == i || a[1] == j) { ret--; } ret -= cnt2[i] + cnt2[j]; ret += mpp2[i][j]; res[i] = min(res[i], ret); res[j] = min(res[j], ret); } } for(int i = 1; i<=m; i++) { int ret = n - cnt1[i]; if((n & 1) && a[n] == i) ret--; res[i] = min(res[i], ret); cout << res[i] << "\n"; } } signed main() { fastio(); int test = 1; //cin>>test; while(test--) { solve(); } }
#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...