Submission #1180436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180436		Szymon_Pilipczuk	Rope (JOI17_rope)	C++20	80 / 100	2293 ms	277432 KiB

rope

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
#define all(a) a.begin(),a.end()
int main()
{
    int n,m;
    cin>>n>>m;
    int c[n];
    vector<int> am(m);
    map<pair<int,int>,int> e;
    map<pair<int,int>,int> e2;
    for(int i =0 ;i<n;i++)
    {
        cin>>c[i];
        c[i]--;
        am[c[i]]++;
    }
    if(m == 1)
    {
        cout<<0<<"\n";
        return 0;
    }
    vector<pair<int,int>> w;
    for(int i = 0;i<m;i++)
    {
        w.push_back({am[i],i});
    }
    sort(all(w));
    reverse(all(w));
    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++)
    {
        for(int j = 0;j<m;j++)
        {
            if(e.find({i,w[j].nd}) == e.end() && w[j].nd != i)
            {
                e[{i,w[j].nd}] = 0;
                break;
            }
        }
    }
    for(int i = 0;i<m;i++)
    {
        for(int j = 0;j<m;j++)
        {
            if(e2.find({i,w[j].nd}) == e2.end() && w[j].nd != i)
            {
                e2[{i,w[j].nd}] = 0;
                break;
            }
        }
    }
    int i = 0;
    vector<int> tans(m,1e9);
    int ans = 1e9;
    for(auto [key,value] : e)
    {
        while(key.st != i)
        {
            tans[i] = ans;
            ans = 1e9;
            i++;
        }
        ans = min(ans,n-am[i]-am[key.nd]+value);
    }
    tans[i] = min(tans[i],ans);
    ans = 1e9;
    i = 0;
    for(auto [key,value] : e2)
    {
        while(key.st != i)
        {
            tans[i] = min(tans[i],ans);
            ans = 1e9;
            i++;
        }
        ans = min(ans,n-am[i]-am[key.nd]+value);
    }
    tans[i] =min(tans[i],ans);
    for(int i =0 ;i<m;i++)
    {
        cout<<tans[i]<<"\n";
    }
}

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