Submission #1180088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180088		Szymon_Pilipczuk	Rope (JOI17_rope)	C++20	0 / 100	0 ms	320 KiB

rope

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
int main()
{
    int n,m;
    cin>>n>>m;
    int c[n];
    vector<int> am(m);
    vector<map<int,int>> e(m);
    vector<map<int,int>> e2(m);
    pair<int,int> mx;
    pair<int,int> mx2;
    for(int i =0 ;i<n;i++)
    {
        cin>>c[i];
        c[i]--;
        am[c[i]]++;
        if(am[c[i]] > mx.st)
        {
            mx2 = mx;
            mx = {am[c[i]],c[i]};
        }
        else if(am[c[i]] > mx2.st)
        {
            mx2 = {am[c[i]],c[i]};
        }
    }
    for(int i = 0;i<n;i++)
    {
        if(i < n-1)
        {
            if(c[i+1] != c[i])
            {
                if(i%2 == 0)
                {
                    e[c[i]][c[i+1]]++;
                    e[c[i+1]][c[i]]++;
                }
                else
                {
                    e2[c[i]][c[i+1]]++;
                    e2[c[i+1]][c[i]]++;
                }
            }
        }
    }
    for(int i = 0;i<m;i++)
    {
        if(i!= mx.nd && e[i].find(mx.nd) == e[i].end())
        {
            e[i][mx.nd] = 0;
        }
        else if(i == mx.nd && e[i].find(mx2.nd) == e[i].end())
        {
            e[i][mx2.nd] = 0;
        }
        if(i!= mx.nd && e2[i].find(mx.nd) == e2[i].end())
        {
            e2[i][mx.nd] = 0;
        }
        else if(i == mx.nd && e2[i].find(mx2.nd) == e2[i].end())
        {
            e2[i][mx2.nd] = 0;
        }
    }
    for(int i = 0;i<m;i++)
    {
        int ans = 1e9;
        for(auto [key,value] : e[i])
        {
            int cu = n-am[i]-am[key]+value;
            if(n%2 == 1 && (c[n-1] !=  key && c[n-1] != i))
            {
                cu++;
            }
            ans = min(ans,cu);
            //cout<<cu<<" "<<n<<" "<<am[i]<<" "<<am[key]<<" "<<key<<" "<<value<<"\n";
        }
        //cout<<ans<<"\n";
        int ans2 = 1e9;
        for(auto [key,value] : e2[i])
        {
            int cu =n-am[i]-am[key]+value;
            if(n%2 == 0)
            {
                if(c[n-1] != key && c[n-1] != i)
                {
                    cu++;
                }
            }
            if(c[0] != key &&c[0] != i)
            {
                cu++;
            }
            ans2 = min(ans2,cu);
        }
        //cout<<ans2<<"\n";
        cout<<min(ans,ans2)<<"\n";
    }
}

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