oj.uz

Submission #44885

# Submission time Handle Problem Language Result Execution time Memory
44885 2018-04-09T02:36:53 Z TAMREF Savez (COCI15_savez) C++11
120 / 120
 176 ms 36516 KB 
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
typedef pair<ll,ll> pll;

const int mx = 2e6 + 5;
const ll mod[2] = {1000000007LL,1610612741LL};

map<ll,int> M;

char S[mx];
unsigned int pfx[2][mx], sfx[2][mx];
unsigned int pow_27[2][mx] = {{1u},{1u}};
int n;

void init(){
    scanf("%d",&n);
    for(int b=0;b<2;b++)
        for(int i=1;i<mx;i++)
            pow_27[b][i] = 27LL * pow_27[b][i-1] % mod[b];
}

void update(){
    scanf("%*c%s",S+1);
    int l = strlen(S+1);

    for(int b = 0; b < 2 ; b++)
    for(int i = 1; i <= l; i++){
        pfx[b][i] = (27LL * pfx[b][i-1] + (S[i] - 'A' + 1)) % mod[b];
    }

    sfx[0][l+1] = sfx[1][l+1] = 0;

    for(int b = 0; b <  2; b++)
    for(int i = l; i >= 1; i--){
        sfx[b][i] = ((ll)pow_27[b][l-i] * (S[i] - 'A' + 1) + sfx[b][i+1]) % mod[b];
    }

    int dlen = 1;
    for(int i = 1; i <= l; i++){
        if(pfx[0][i] == sfx[0][l+1-i] && pfx[1][i] == sfx[1][l+1-i]){
            dlen = max(dlen, M[(ll)pfx[0][i] << 32 | pfx[1][i]] + 1);
        }
    }
    M[(ll)pfx[0][l] << 32 | pfx[1][l]] = dlen;
}

void output(){
    int ans = 1;
    for(auto p : M){
        ans = max(ans, p.second);
    }
    printf("%d\n",ans);
}

int main(){
    init();
    for(int i=1;i<=n;i++){
        update();
    }
    output();
}

Compilation message

savez.cpp: In function 'void init()':
savez.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
savez.cpp: In function 'void update()':
savez.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*c%s",S+1);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15992 KB Output is correct
2 Correct 45 ms 16116 KB Output is correct
3 Correct 45 ms 16168 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16212 KB Output is correct
2 Correct 45 ms 16212 KB Output is correct
3 Correct 47 ms 16224 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 17328 KB Output is correct
2 Correct 173 ms 18484 KB Output is correct
3 Correct 176 ms 19324 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19324 KB Output is correct
2 Correct 99 ms 20392 KB Output is correct
3 Correct 133 ms 21496 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 22212 KB Output is correct
2 Correct 82 ms 23248 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 24236 KB Output is correct
2 Correct 80 ms 25212 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 26236 KB Output is correct
2 Correct 78 ms 27300 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 28480 KB Output is correct
2 Correct 80 ms 29404 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 30556 KB Output is correct
2 Correct 87 ms 31736 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 33080 KB Output is correct
2 Correct 101 ms 34444 KB Output is correct
3 Correct 152 ms 36516 KB Output is correct