oj.uz

Submission #197996

# Submission time Handle Problem Language Result Execution time Memory
197996 2020-01-24T12:50:38 Z Ruxandra985 Matching (CEOI11_mat) C++14
100 / 100
 1264 ms 40312 KB 
#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 - p[l] - 1] , -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++){
        //if (i == 35)
          //  printf ("a");
        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 - p[l] - 1] , -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 - p[l]] , -1);
                //printf ("%d " , i - l + j - p[l]);
            }
            l = p[l];
        }
    }
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=sol;i++)
        fprintf (fout,"%d " , ok[i]);
    return 0;
}

Compilation message

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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8312 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Correct 10 ms 8184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8540 KB Output is correct
2 Correct 18 ms 8440 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8568 KB Output is correct
2 Correct 19 ms 8440 KB Output is correct
3 Correct 10 ms 8184 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11384 KB Output is correct
2 Correct 95 ms 11000 KB Output is correct
3 Correct 156 ms 12484 KB Output is correct
4 Correct 157 ms 12428 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12024 KB Output is correct
2 Correct 142 ms 11776 KB Output is correct
3 Correct 115 ms 12112 KB Output is correct
4 Correct 111 ms 13048 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 12124 KB Output is correct
2 Correct 107 ms 11728 KB Output is correct
3 Correct 125 ms 11900 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 21668 KB Output is correct
2 Correct 1264 ms 40312 KB Output is correct
3 Correct 499 ms 22136 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 21376 KB Output is correct
2 Correct 753 ms 22796 KB Output is correct
3 Correct 1231 ms 36732 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 20188 KB Output is correct
2 Correct 520 ms 33500 KB Output is correct
3 Correct 664 ms 26340 KB Output is correct
4 Correct 741 ms 38376 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 20728 KB Output is correct
2 Correct 658 ms 26864 KB Output is correct
3 Correct 263 ms 17128 KB Output is correct
4 Correct 805 ms 38036 KB Output is correct