Submission #1180068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180068		user736482	Rope (JOI17_rope)	C++20	0 / 100	0 ms	324 KiB

rope

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll int
#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)}]));
        }
    }
    for(ll i=1;i<m;i++)cout<<ans[i]<<"\n";
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:11:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000099' to '-1486618525' [-Woverflow]
   11 | #define INFL 1000000000000000099LL
      |              ^~~~~~~~~~~~~~~~~~~~~
rope.cpp:38:16: note: in expansion of macro 'INFL'
   38 |         ans[i]=INFL;
      |                ^~~~

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