Submission #1180077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180077		user736482	Rope (JOI17_rope)	C++20	100 / 100	1491 ms	234420 KiB

rope

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,k,m;
vector<ll>v2;
ll cnt[1000007];
ll ans[1000007];
vector<pair<ll,ll>>licz;
vector<pair<ll,ll>>v;//kolor,ile
map<pair<ll,ll>,ll>mp[2];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    m++;
    cin>>a;
    v2.pb(a);
    cnt[a]++;
    for(ll i=1;i<n;i++){
        cin>>a;
        cnt[a]++;
        mp[i%2][{min(a,v2.back()),max(a,v2.back())}]++;
        v2.pb(a);
    }
    v.pb({v2.back(),c});
    ll sm=0;
    for(ll i=1;i<=m;i++){
        licz.pb({cnt[i],i});
        ans[i]=INFL;
    }
    sort(licz.begin(),licz.end());
    reverse(licz.begin(),licz.end());
    for(ll i=1;i<=m;i++){
        
        for(ll j=0;j<=m;j++){
            if(licz[j].ss==i)continue;
            ans[i]=min(ans[i],n-cnt[i]-licz[j].ff+min(mp[0][{min(i,licz[j].ss),max(i,licz[j].ss)}],mp[1][{min(i,licz[j].ss),max(i,licz[j].ss)}]));
        
          if(min(mp[0][{min(i,licz[j].ss),max(i,licz[j].ss)}],mp[1][{min(i,licz[j].ss),max(i,licz[j].ss)}])==0)break;
        }
    }
    for(ll i=1;i<m;i++)cout<<ans[i]<<"\n";
}

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