Submission #1069445

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

mat

#include <bits/stdc++.h>

/*
 Constant factor optimisation
 
 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;
int n,m;
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin>>n>>m;
    long long base=174320687;
    std::vector<long long> muls1(m+1,1);
    std::vector<long long> muls2(m+1,1);
    long long cur1=1,cur2=1;
    for(int i=0;i<=m;i++){
        muls1[i]=cur1;
        muls2[i]=cur2;
        cur1=(cur1*base)%mod1;
        cur2=(cur2*base)%mod2;
    }
    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)*muls1[last];
            targhash2+=(long long)(x-last)*muls2[last];
            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-=muls1[oldpos]*(nxtpos-oldpos)%mod1;
                curhash2-=muls2[oldpos]*(nxtpos-oldpos)%mod2;
            }
            if(curit!=numinds.begin()){//break link before
                auto curit2=curit;
                --curit2;
                int befpos=curit2->second;
                curhash1-=muls1[befpos]*(oldpos-befpos)%mod1;
                curhash2-=muls2[befpos]*(oldpos-befpos)%mod2;
                if(curit!=numinds.end()){//make link
                    int nxtpos=curit->second;
                    curhash1+=muls1[befpos]*(nxtpos-befpos)%mod1;
                    curhash2+=muls2[befpos]*(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-=muls1[befpos]*(aftpos-befpos)%mod1;
                curhash2-=muls2[befpos]*(aftpos-befpos)%mod2;
            }
            curhash1+=muls1[befpos]*(curpos-befpos)%mod1;
            curhash2+=muls2[befpos]*(curpos-befpos)%mod2;
        }
        if(lb!=numinds.end()){
            int aftpos=lb->second;
            curhash1+=muls1[curpos]*(aftpos-curpos)%mod1;
            curhash2+=muls2[curpos]*(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: 0 / 9
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 10 / 10