Submission #1315612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315612		aren_dance	Bliskost (COI23_bliskost)	C++20	100 / 100	131 ms	16584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=6e5+1;
#define ll long long
vector<int> d;
int cur=0;
string quary(string a,string b){
    vector<int> u,v;
    u.resize(a.size());
    v.resize(b.size());
    d.resize(b.size());
    int n=a.size();
    for(int i=0;i<n;++i){
        u[i]=a[i]-'a';
        v[i]=b[i]-'a';
        d[i]=(a[i]-b[i]+26)%26;
    }
    ll g=d[n-1];
    for(int i=1;i<n;++i){
        if(i%2==1){
            cur+=d[i];
        }
        else{
            cur-=d[i];
        }
    }
    for(int i=n-2;i>=1;--i){
        g=(d[i]-g+26)%26;
    }
    if(g==d[0]){
        return "da";
    }
    return "ne";
}
int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    string a,b;
    cin>>a>>b;
    cout<<quary(a,b)<<'\n';
    while(q--){
        int p;char c;
        cin>>p>>c;
        a[p-1]=c;
        if(p!=1){
        if((p-1)%2==1){
            cur-=d[(p-1)];
        }
        else{
            cur+=d[(p-1)];
        }
    }
        int e=c-'a';
        int f=b[p-1]-'a';
        d[(p-1)]=(e-f+26)%26;
        if(p!=1){
        if((p-1)%2==0){
            cur-=d[(p-1)];
        }
        else{
            cur+=d[(p-1)];
        }
    }

        if((cur+26000000)%26==d[0]){
            cout<<"da"<<'\n';
        }
        else{
            cout<<"ne"<<'\n';
        }
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 17 / 17
• Subtask 6: 43 / 43