Submission #51001

#	Time	Username	Problem	Language	Result	Execution time	Memory
51001		Diuven	Rope (JOI17_rope)	C++11	100 / 100	1807 ms	197656 KiB

rope

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MX=1000010, inf=2e9;

int n, m, A[MX];
int C[2][MX];
int ans[MX];
int idx[2][MX];

vector<int> G[2][MX];

void init(){
    fill(ans+1, ans+m+1, inf);
    for(int i=0; i<=n; i++){
        C[i%2][A[i]]++; C[i%2][A[i+1]]++;
    }
    for(int i=1; i<n; i++){
        if(A[i]==A[i+1]) continue;
        G[i%2][A[i]].push_back(A[i+1]);
        G[i%2][A[i+1]].push_back(A[i]);
    }
    iota(idx[0]+1, idx[0]+m+1, 1);
    iota(idx[1]+1, idx[1]+m+1, 1);
    sort(idx[0]+1, idx[0]+m+1, [](int a, int b){ return C[0][a]>C[0][b]; });
    sort(idx[1]+1, idx[1]+m+1, [](int a, int b){ return C[1][a]>C[1][b]; });
}

void solve(){
    int adj[MX]={};

    for(int v=1; v<=m; v++){
        for(int k=0; k<=1; k++){
            int mx=0;
            for(int x:G[k][v]) adj[x]++;
            for(int x:G[k][v]){
                mx=max(mx, C[k][x]-adj[x]);
            }
            for(int i=1; i<=m; i++){
                int x=idx[k][i];
                if(x!=v && adj[x]==0){
                    mx=max(mx, C[k][x]);
                    break;
                }
            }
            for(int x:G[k][v]) adj[x]--;
            ans[v]=min(ans[v], n-C[k][v]-mx);
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>A[i];
    init();
    solve();
    
    for(int i=1; i<=m; i++) cout<<ans[i]<<'\n';

    return 0;
}

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