Submission #1047030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047030		isaachew	Matching (CEOI11_mat)	C++17	100 / 100	1352 ms	65536 KiB

mat

#include <bits/stdc++.h>

/*
 Linked list thing
 Every index has difference between its index and index of next number up
 Hash
 
 
 3 1 2 -> 1 0 -2
          1 2  3
 */
std::vector<long long> inddiffs;//indices of greater nums
long long mod1=1000000007,mod2=1000000009;
long long binexp(long long a,int p,int mod){
    long long result=1;
    while(p){
        if(p&1)result*=a;
        a*=a;
        result%=mod;
        a%=mod;
        p>>=1;
    }
    return result;
}
int n,m;
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    long long base=145023607;
    std::cin>>n>>m;
    std::vector<int> pattern;
    std::vector<int> nums;
    long long targhash1=0,targhash2=0;
    int last=-1;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        x--;
        if(last!=-1){
            targhash1+=(long long)(x-last)*binexp(base,last,mod1);
            targhash2+=(long long)(x-last)*binexp(base,last,mod2);
            targhash1%=mod1;
            targhash2%=mod2;
        }
        last=x;
    }
    std::map<int,int> numinds;
    std::vector<int> results;
    long long curhash1=0,curhash2=0;
    for(int i=0;i<m;i++){
        int x;
        std::cin>>x;
        nums.push_back(x);
        if(i>=n){
            auto curit=numinds.find(nums[i-n]);
            int oldpos=curit->second;
            curit=numinds.erase(curit);
            if(curit!=numinds.end()){//break link after
                int nxtpos=curit->second;
                curhash1-=binexp(base,oldpos,mod1)*(nxtpos-oldpos)%mod1;
                curhash2-=binexp(base,oldpos,mod2)*(nxtpos-oldpos)%mod2;
            }
            if(curit!=numinds.begin()){//break link before
                auto curit2=curit;
                --curit2;
                int befpos=curit2->second;
                curhash1-=binexp(base,befpos,mod1)*(oldpos-befpos)%mod1;
                curhash2-=binexp(base,befpos,mod2)*(oldpos-befpos)%mod2;
                if(curit!=numinds.end()){//make link
                    int nxtpos=curit->second;
                    curhash1+=binexp(base,befpos,mod1)*(nxtpos-befpos)%mod1;
                    curhash2+=binexp(base,befpos,mod2)*(nxtpos-befpos)%mod2;
                }
            }
        }
        auto lb=numinds.lower_bound(x);//smallest >x?
        int curpos=i;
        if(lb!=numinds.begin()){
            auto lb2=lb;
            --lb2;
            int befpos=lb2->second;
            if(lb!=numinds.end()){
                int aftpos=lb->second;
                curhash1-=binexp(base,befpos,mod1)*(aftpos-befpos)%mod1;
                curhash2-=binexp(base,befpos,mod2)*(aftpos-befpos)%mod2;
            }
            curhash1+=binexp(base,befpos,mod1)*(curpos-befpos)%mod1;
            curhash2+=binexp(base,befpos,mod2)*(curpos-befpos)%mod2;
        }
        if(lb!=numinds.end()){
            int aftpos=lb->second;
            curhash1+=binexp(base,curpos,mod1)*(aftpos-curpos)%mod1;
            curhash2+=binexp(base,curpos,mod2)*(aftpos-curpos)%mod2;
        }
        numinds[x]=i;
        if(i>=n-1){
            targhash1=(targhash1%mod1+mod1)%mod1;//make sure non-negative
            targhash2=(targhash2%mod2+mod2)%mod2;
            curhash1=(curhash1%mod1+mod1)%mod1;
            curhash2=(curhash2%mod2+mod2)%mod2;
            if(curhash1==targhash1&&curhash2==targhash2){
                results.push_back(i-n+1);
            }
            targhash1*=base;//move query over one space
            targhash2*=base;
        }
    }
    std::cout<<results.size()<<'\n';
    for(int i:results)std::cout<<i+1<<' ';
    std::cout<<'\n';
}

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