Submission #197938

#	Time	Username	Problem	Language	Result	Execution time	Memory
197938		Ruxandra985	Matching (CEOI11_mat)	C++14	0 / 100	558 ms	28356 KiB

mat

#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;
int aib1[DIMN] , aib2[DIMN] , v[DIMN] , w[DIMN] , ok[DIMN] , aux[DIMN] , p[DIMN];
void update (int aib[] , int i , int x){

    for (;i<=1000000;i = i + (i & (-i)))
        aib[i]+=x;

}
int query (int aib[] , int i){
    int sol = 0;
    if (!i)
        return 0;
    for (;i;i = i - (i & (-i)))
        sol+=aib[i];
    return sol;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , x, elem = 0 , j , l , st , dr , mid , sol = 0;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=n;i++){ /// faci asta pt ca v e clar permutare
        fscanf (fin,"%d",&x);
        v[x] = i;
    }

    /// acum e mom sa citesc pe w si sa il normalizez

    for (i=1;i<=m;i++){
        fscanf (fin,"%d",&w[i]);
        aux[i] = w[i];
    }
    sort (aux + 1 , aux + m + 1);
    elem = 0;
    for (i=1;i<=m;i++){
        if (!elem || aux[i] != aux[i-1])
            aux[++elem] = aux[i];
    }
    for (i=1;i<=m;i++){
        st = 1;
        dr = elem;
        while (st <= dr){
            mid = (st + dr)/2;
            if (aux[mid] == w[i]){
                w[i] = mid;
                break;
            }
            else if (aux[mid] < w[i])
                st = mid + 1;
            else dr = mid - 1;
        }
    }
    /// ai normalizat
    /// aib1 e pt l , aib2 e pt i
    l = 0;
    for (i=2;i<=n;i++){

        while (l && query(aib1 , v[l+1]) != query(aib2 , v[i])){
            for (j = p[l] + 1 ; j <= l ; j++){ /// anulezi
                update (aib1 , v[j] , -1);
                update (aib2 , v[i - l + j] , -1);
            }
            l = p[l];
        }

        if (query(aib1 , v[l+1]) == query(aib2 , v[i])){
            l++;
            update (aib1 , v[l] , 1);
            update (aib2 , v[i] , 1);
        }

        p[i] = l;
    }

    memset (aib1 , 0 , sizeof(aib1));
    memset (aib2 , 0 , sizeof(aib2));

    /// aib1 e pt l , aib2 e pt i
    l = 0;
    sol = 0;
    for (i=1;i<=m;i++){

        while (l && query(aib1 , v[l+1]) != query(aib2 , w[i])){
            for (j = p[l] + 1 ; j <= l ; j++){ /// anulezi
                update (aib1 , v[j] , -1);
                update (aib2 , w[i - l + j] , -1);
            }
            l = p[l];
        }

        if (query(aib1 , v[l+1]) == query(aib2 , w[i])){
            l++;
            update (aib1 , v[l] , 1);
            update (aib2 , w[i] , 1);
        }

        if (l == n){
            ok[++sol] = i - l + 1;
            for (j = p[l] + 1 ; j <= l ; j++){ /// anulezi
                update (aib1 , v[j] , -1);
                update (aib2 , w[i - l + j] , -1);
            }
            l = p[l];
        }
    }
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=sol;i++)
        fprintf (fout,"%d " , ok[i]);
    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:25: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
mat.cpp:27:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&x);
         ~~~~~~~^~~~~~~~~~~~~
mat.cpp:34:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&w[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10