Submission #226544

#	Time	Username	Problem	Language	Result	Execution time	Memory
226544		Ruxandra985	Rope (JOI17_rope)	C++14	0 / 100	21 ms	23936 KiB

rope

#include <bits/stdc++.h>

using namespace std;
int v[1000010] , fii[1000010] , sol[1000010];
int n , m;
vector <int> w[1000010] , now;
pair <int,int> f[1000010] , fi[1000010];
void solve (int caz){
    int i , first , curr , idx , x , fmax , maxi , j;

    for (i = 1 ; i <= m ; i++)
        w[i].clear();

    for (i = caz ; i < n ; i += 2 ){

        if (v[i] == v[i + 1]){
            w[v[i]].push_back(i); /// unde incepe perechea
        }
        else {
            w[v[i]].push_back(i); /// unde incepe perechea
            w[v[i + 1]].push_back(i); /// unde incepe perechea
        }


    }

    if (i == n)
        w[v[n]].push_back(n);

    /// in w, tin pt fiecare culoare, in ce perechi e

    for (i = 1 ; i <= m ; i++){

        //if (caz == 2 && i == 3)
          //  printf ("a");

        curr = 0;
        first = 2 * w[i].size();
        maxi = 0;
        fmax = 0;
        now.clear();

        /// as vrea sa tin cea mai mare val a unui elem modificat

        for (j = 0 ; j < w[i].size() ; j++){

            idx = w[i][j];

            x = v[idx];
            if (f[x].second != i){
                f[x] = make_pair(1 , i);
                now.push_back(x);
            }
            else f[x].first++;



            if (x != i)
                curr++;

            x = v[idx + 1];
            if (f[x].second != i){
                f[x] = make_pair(1 , i);
                now.push_back(x);
            }
            else f[x].first++;

            if (x != i)
                curr++;

        }

        /// in now ai valorile schimbate !!!!

        if (caz == 2){
            x = v[1];
            if (f[x].second != i){
                f[x] = make_pair(0 , i);
                now.push_back(x);
            }



            if (x == i)
                first++;
        }

        /// in first tii cate elem iau valoarea i
        /// curr = cate elemente ai schimbat in i


        for (j = 0 ; j < now.size() ; j++){

            x = now[j];

            if (maxi < fii[x] - f[x].first){
                maxi = fii[x] - f[x].first;
                fmax = x;
            }

        }

        j = m;
        while (j && f[ fi[j].second ].second == i)
            j--;

        if (j){

            if (maxi < fi[j].first){
                maxi = fi[j].first;
                fmax = fi[j].second;
            }
        }




        sol[i] = min(sol[i] , curr + n - first - maxi);
        sol[fmax] = min(sol[fmax] , curr + n - first - maxi);

    }



}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i;
    fscanf (fin,"%d%d",&n,&m);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        fi[v[i]].first++;
        fii[v[i]]++;
    }

    for (i = 1 ; i <= m ; i++)
        fi[i].second = i;

    sort (fi + 1 , fi + m + 1);

    if (m == 1){ /// sa scap
        fprintf (fout,"0");
        return 0;
    }

    for (i = 1 ; i <= m ; i++)
        sol[i] = 2000000000;

    solve (1);

    for (i = 1 ; i <= m ; i++){
        f[i].second = 0;
    }


    solve (2);

    for (i = 1 ; i <= m ; i++)
        fprintf (fout,"%d\n",sol[i]);

    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'void solve(int)':
rope.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0 ; j < w[i].size() ; j++){
                      ~~^~~~~~~~~~~~~
rope.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0 ; j < now.size() ; j++){
                      ~~^~~~~~~~~~~~
rope.cpp: In function 'int main()':
rope.cpp:133:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
rope.cpp:135:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~

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