Submission #1001118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001118		Otalp	Rope (JOI17_rope)	C++14	100 / 100	779 ms	159232 KiB

rope

#include<bits/stdc++.h>
using namespace std;
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define h(a, b) (ll)a * 1e7 + b
 
unordered_map<ll, int> dp[2];
int cnt[1000001];
int a[1000001];
vector<int> d[1000001];
int g[1000001];
 
bool cmp(int a, int b){
    if(cnt[a] == cnt[b]) return a > b;
    return cnt[a] > cnt[b];
}
 
//ll h(ll a, ll b){ //hynya
//    return a * 1e7 + b;
//}
 
void solve(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        cnt[a[i]] ++;
    }
    for(int i=1; i<=m; i++){
        g[i] = i;
    }
    sort(g + 1, g + 1 + m, cmp);
 
    for(int i=1; i+1<=n; i+=2){
        int l=a[i], r=a[i + 1];
        if(dp[1].count(h(l, r))){
            d[l].pb(r);
            d[r].pb(l);
        }
        dp[1][h(l, r)] ++;
        dp[1][h(r, l)] ++;
    }
    for(int i=2; i+1<=n; i+=2){
        int l=a[i], r=a[i + 1];
        if(dp[1].count(h(l, r)) or dp[0].count(h(l, r))){
            d[l].pb(r);
            d[r].pb(l);
        }
        dp[0][h(l, r)] ++;
        dp[0][h(r, l)] ++;
    }
    ll dd = 0;
    for(int i=1; i<=m; i++) dd += d[i].size();
    if(dd > 2e6) return;
    if(dp[0].size() + dp[1].size() > 2e6) return;
    for(int i=1; i<=m; i++){
        d[i].pb(i);
        sort(d[i].begin(), d[i].end(), cmp);
    }
    for(int i=1; i<=m; i++){
        int ans = n - cnt[i];
        int ls = 1;
        for(int j: d[i]){
            while(ls <= m and g[ls] == j) ls++;
            if(j == i) continue;
            for(int k=0; k<2; k++){ 
                ans = min(ans, n-cnt[i]-cnt[j]+dp[k][h(i, j)]);
            }
        }
        if(ls <= m) ans = min(ans, n-cnt[i]-cnt[g[ls]]);
        cout<<ans<<'\n';
    }
}
 
 
signed main(){
    ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
    solve();
}

Compilation message (stderr)

rope.cpp:3: warning: ignoring '#pragma optimization_level ' [-Wunknown-pragmas]
    3 | #pragma optimization_level 3
      |

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20