Submission #226518

#	Time	Username	Problem	Language	Result	Execution time	Memory
226518		Ruxandra985	Rope (JOI17_rope)	C++14	55 / 100	2590 ms	12684 KiB

rope

#include <bits/stdc++.h>

using namespace std;
int v[1000010] , f[1000010] , sol[1000010] , w[1000010];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , j , curr , fmax , maxi , first;
    fscanf (fin,"%d%d",&n,&m);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
    }

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

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

        //if (i == 9)
          //  printf ("a");

        curr = 0;
        maxi = 0;
        fmax = 0;
        first = 0;

        memset (f , 0 , sizeof(f));

        /// cazul 1 : mereu 2k = 2k - 1

        for (j = 2 ; j <= n ; j += 2){

            /// v[j] = v[j - 1]

            if (v[j] == i || v[j - 1] == i){ /// astea 2 devin cu i
                curr = curr + (v[j] != i) + (v[j - 1] != i);
                first += 2;
            }
            else {
                f[v[j]]++;
                f[v[j - 1]]++;

                if (f[v[j]] > maxi){
                    maxi = f[v[j]];
                    fmax = v[j];
                }

                if (f[v[j - 1]] > maxi){
                    maxi = f[v[j - 1]];
                    fmax = v[j - 1];
                }

            }

        }
        if (n % 2){ /// ai sarit peste
            if (v[n] == i)
                first++;
            else {
                f[v[n]]++;
                if (f[v[n]] > maxi){
                    maxi = f[v[n]];
                    fmax = v[n];
                }

            }
        }

        curr = curr + n - first - f[fmax];

        sol[i] = min(sol[i] , curr);
        sol[fmax] = min(sol[fmax] , curr);

        /// --------------------------------------------------------------------------

        curr = 0;
        maxi = 0;
        fmax = 0;
        first = 0;

        memset (f , 0 , sizeof(f));

        /// cazul 1 : mereu 2k + 1 = 2k

        for (j = 2 ; j < n ; j += 2){

            /// v[j] = v[j - 1]

            if (v[j] == i || v[j + 1] == i){ /// astea 2 devin cu i
                curr = curr + (v[j] != i) + (v[j + 1] != i);
                first += 2;
            }
            else {
                f[v[j]]++;
                f[v[j + 1]]++;

                if (f[v[j]] > maxi){
                    maxi = f[v[j]];
                    fmax = v[j];
                }

                if (f[v[j + 1]] > maxi){
                    maxi = f[v[j + 1]];
                    fmax = v[j + 1];
                }

            }

        }

        if (v[1] == i)
            first++;
        else {
            f[v[1]]++;
            if (f[v[1]] > maxi){
                maxi = f[v[1]];
                fmax = v[1];
            }

        }


        if (n % 2 == 0){ /// ai sarit peste
            if (v[n] == i)
                first++;
            else {
                f[v[n]]++;
                if (f[v[n]] > maxi){
                    maxi = f[v[n]];
                    fmax = v[n];
                }

            }
        }

        curr = curr + n - first - f[fmax];

        sol[i] = min(sol[i] , curr);
        sol[fmax] = min(sol[fmax] , curr);




    }

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

    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:10: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:12: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: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20