oj.uz

Submission #739154

# Submission time Handle Problem Language Result Execution time Memory
739154 2023-05-10T04:35:32 Z huynhyen1609 Matching (CEOI11_mat) C++14
100 / 100
 1022 ms 65536 KB 
/*
                                 ..
                        .:^!7?JJJYJJJJ?77!!~^.
                   .:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:.
                 :!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~.
               :?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!.
             ^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^
           ~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^
         ^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7.
        !PY?777?77!7!7J?7!7?????JJ??7J??J^:.           .:!7?75GY:
      .JPJ!7!7?7?7!7!????????J?7??7J?YJ~.                .:!7?JGP^
     .JP?!7!!??7J7!!!?7J????7J7!!?!?7?7.                 .  ^??YG5:
     !P??7777?77??777?7?!7!777!?7J??J?^              :~~:  . ^?7YGY.
    :PY7??77!7~~:::.....:^^~!7??????J?^        .   .7PGGPY: . !?JPB~
   .Y5!!Y77!~:..            .:~7JJJ??J!.       . . .5GGGGP^ ..:J?JBJ
   ~G?!!?7!^.                  .^7JJYYJ7:.      . ..:~???~^^:..77?G5.
   !G!7?77:                     ..?J7~^~!77: .  .. ..^~~~~~~~:.!75B!
   !P77J7^                     ..~?:::^~!7?^ ........^~^^^^^:.^JYG?.
   !G???!:      .~77!:.        ..7?7?77~:....................^JPJ~
   :P5??7:     .JGGGGP!        ......  ..................:^!JP?^
    7BJ7J~     .JGGGGG~       . .....................::::^!7?JJ?!^.
    .YG?Y7^     .~7??~:::.     ..  .... ... ....::::::::::::^?~^!?J7:
     :PPJ??:    ..:^^^^^^:     .  .... ....::::^::::::::.:::^JP~..:75~
      :YGYJ?^.  .^^^^^^^:.        .....:::::::::::...:::..:.::JP!~~7Y~
        ~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~.
         :75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5?
           ?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^
           ~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY
            :!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP.
               :5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P:
               .P7::::::::::^::^^::::::::::::::::.:.........:::::J5.
           .   ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^
               :P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^
               .!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G?
                 ~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!.
                  .~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^  ..
                   .777?5J??YYYYY5?7777!!!!~!~~^^::.  .::
                        :!!~:.:^^:

        PENGUIN SO CUTE, I LOVE PENGUIN
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME ""
#define int long long
#define pii pair<int,int>
const int oo=1e9;
const int base=1e4;
const int mod=1e9+7;
const int N=1e6;
const int LG=18;
const int Sqrt=350;
//int hx[]={0,0,1,-1,1,1,-1,-1},hy[]={1,-1,0,0,1,-1,1,-1};
int n,m,a[N+5],p[N+4],tree[4*N+5],cnt[4*N+5];
pii b[N+5];
bool cmp(pii a,pii b)
{
    return a.se<b.se;
}
void up(int id,int l,int r,int k,int val)
{
    if(l==r)
    {
        tree[id]=val;
        if(val)cnt[id]=1;
        else cnt[id]=0;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid)up(id*2,l,mid,k,val);
    else up(id*2+1,mid+1,r,k,val);
    tree[id]=(tree[id*2]*p[cnt[id*2+1]]%mod+tree[id*2+1])%mod;
    cnt[id]=cnt[id*2]+cnt[id*2+1];
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen(""NAME".inp","r",stdin);
    //freopen(""NAME".out","w",stdout);
    cin>>n>>m;
    int h=0;
    for(int i=1;i<=n;++i)
    {
        int x;cin>>x;
        h=(h*base%mod+x)%mod;
        a[x]=i;
    }
    p[0]=1;
    for(int i=1;i<=m;++i)p[i]=p[i-1]*base%mod;
    //nén dãy b
    for(int i=1;i<=m;++i)cin>>b[i].fi,b[i].se=i;
    sort(b+1,b+m+1);
    for(int i=1;i<=m;++i)b[i].fi=i;
    sort(b+1,b+m+1,cmp);

    int sum=0;
    for(int i=0;i<n;++i)sum=(sum+p[i])%mod;

    queue<int>q;
    for(int i=1;i<=m;++i)
    {
        up(1,1,m,b[i].fi,i);
        if(i>=n)
        {
            int tmp=(tree[1]-sum*(i-n)%mod+mod)%mod;
            if(tmp==h)q.push(i-n+1);
            //cout<<tmp<<' '<<h<<'\n';
            up(1,1,m,b[i-n+1].fi,0);
        }
    }
    cout<<q.size()<<'\n';
    while(!q.empty())
    {
        cout<<q.front()<<' ';
        q.pop();
    }
}
/*
         ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/
/*
6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20
*/

Compilation message

mat.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2016 KB Output is correct
2 Correct 11 ms 1972 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1944 KB Output is correct
2 Correct 13 ms 2016 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 13584 KB Output is correct
2 Correct 122 ms 13388 KB Output is correct
3 Correct 200 ms 14044 KB Output is correct
4 Correct 174 ms 13996 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 14548 KB Output is correct
2 Correct 205 ms 13700 KB Output is correct
3 Correct 132 ms 14068 KB Output is correct
4 Correct 137 ms 16532 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 14440 KB Output is correct
2 Correct 126 ms 13892 KB Output is correct
3 Correct 135 ms 13764 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 59676 KB Output is correct
2 Correct 896 ms 64840 KB Output is correct
3 Correct 833 ms 51964 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 58320 KB Output is correct
2 Correct 1022 ms 57112 KB Output is correct
3 Correct 889 ms 64516 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 58764 KB Output is correct
2 Correct 686 ms 65536 KB Output is correct
3 Correct 915 ms 57032 KB Output is correct
4 Correct 531 ms 64844 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 59280 KB Output is correct
2 Correct 803 ms 57780 KB Output is correct
3 Correct 333 ms 29696 KB Output is correct
4 Correct 607 ms 64056 KB Output is correct