Submission #70669042

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;


const int m = 4;
vector<ull> B = {
    100000007,
    1000000007,
    4594545464,
    3255454435
};



int main(){
    int t;
    cin >> t;
    while(t--){
        string a,b;
        cin >> a >> b;
        int n = a.size();
        string aa = a + a;

        vector<vector<ull>> Bpows(n, vector<ull>(m, 1));
        for(int i = 0; i < n-1; i++){
            for(int j = 0; j < m; j++){
                Bpows[i+1][j] *= Bpows[i][j] * B[j];
            }
        }

        vector<ull> hashA(m, 0);
        vector<ull> hashB(m, 0);

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                hashA[j] += a[i] * Bpows[n-1-i][j];
                hashB[j] += b[i] * Bpows[n-1-i][j];
            }
        }

        bool suc = false;
        for(int i = 0; i < n; i++){
            if(hashA == hashB){
                cout << i << endl;
                suc = true;
                break;
            }
            
            for(int j = 0; j < m; j++){
                hashA[j] -= aa[i] * Bpows[n-1][j];
                hashA[j] *= B[j];
                hashA[j] += aa[i+n];
            }
        }
        if(!suc) cout << -1 << endl;
    }
}

Submission Info

Submission Time
Task E - Shift String
User sakimori_coder
Language C++23 (GCC 15.2.0)
Score 450
Code Size 1334 Byte
Status AC
Exec Time 87 ms
Memory 77640 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 1
AC × 52
Set Name Test Cases
Sample sample_01.txt
All killer_01.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt
Case Name Status Exec Time Memory
killer_01.txt AC 46 ms 3636 KiB
sample_01.txt AC 1 ms 3632 KiB
test_01.txt AC 1 ms 3656 KiB
test_02.txt AC 1 ms 3620 KiB
test_03.txt AC 1 ms 3624 KiB
test_04.txt AC 1 ms 3396 KiB
test_05.txt AC 2 ms 3432 KiB
test_06.txt AC 4 ms 3560 KiB
test_07.txt AC 4 ms 3632 KiB
test_08.txt AC 64 ms 3620 KiB
test_09.txt AC 65 ms 3620 KiB
test_10.txt AC 57 ms 3740 KiB
test_11.txt AC 56 ms 3704 KiB
test_12.txt AC 55 ms 4380 KiB
test_13.txt AC 55 ms 4356 KiB
test_14.txt AC 57 ms 11028 KiB
test_15.txt AC 58 ms 11120 KiB
test_16.txt AC 85 ms 77536 KiB
test_17.txt AC 86 ms 77532 KiB
test_18.txt AC 80 ms 77512 KiB
test_19.txt AC 79 ms 77536 KiB
test_20.txt AC 80 ms 77564 KiB
test_21.txt AC 80 ms 77580 KiB
test_22.txt AC 79 ms 77632 KiB
test_23.txt AC 79 ms 77640 KiB
test_24.txt AC 80 ms 77516 KiB
test_25.txt AC 79 ms 77528 KiB
test_26.txt AC 78 ms 77536 KiB
test_27.txt AC 80 ms 77476 KiB
test_28.txt AC 87 ms 77532 KiB
test_29.txt AC 87 ms 77524 KiB
test_30.txt AC 87 ms 77560 KiB
test_31.txt AC 87 ms 77516 KiB
test_32.txt AC 86 ms 77516 KiB
test_33.txt AC 85 ms 77536 KiB
test_34.txt AC 86 ms 77548 KiB
test_35.txt AC 85 ms 77528 KiB
test_36.txt AC 85 ms 77528 KiB
test_37.txt AC 86 ms 77516 KiB
test_38.txt AC 85 ms 77536 KiB
test_39.txt AC 85 ms 77536 KiB
test_40.txt AC 86 ms 77544 KiB
test_41.txt AC 85 ms 77536 KiB
test_42.txt AC 85 ms 77508 KiB
test_43.txt AC 80 ms 77532 KiB
test_44.txt AC 85 ms 77512 KiB
test_45.txt AC 85 ms 77528 KiB
test_46.txt AC 87 ms 77540 KiB
test_47.txt AC 11 ms 3636 KiB
test_48.txt AC 11 ms 3484 KiB
test_49.txt AC 87 ms 77544 KiB
test_50.txt AC 85 ms 77512 KiB