oj.uz

답안 #320682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320682 2020-11-09T14:00:58 Z phathnv Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 57 ms 15076 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e6 + 1;
const int base = 163;

int t, n;
char s[N];
ll pw[N];

void prepare(){
    pw[0] = 1;
    for(int i = 1; i < N; i++)
        pw[i] = pw[i - 1] * base;
}

void readInput(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
}

void solve(){
    int res = 0;
    int l = 1, r = n, len = 0;
    ll hashedL = 0, hashedR = 0;
    while (l < r){
        hashedL = hashedL * base + s[l++];
        hashedR = hashedR + s[r--] * pw[len++];

        if (hashedL == hashedR){
            hashedL = hashedR = 0;
            res += 2;
            len = 0;
        }
    }
    if (hashedL || l <= r)
        res++;
    printf("%d\n", res);
}

int main(){
    scanf("%d", &t);
    prepare();
    while (t--){
        readInput();
        solve();
    }
    return 0;
}

Compilation message

palindromic.cpp: In function 'void readInput()':
palindromic.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |     scanf("%s", s + 1);
      |     ~~~~~^~~~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 7 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 7 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 6 ms 8300 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 7 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 6 ms 8300 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 7 ms 8300 KB Output is correct
11 Correct 7 ms 8192 KB Output is correct
12 Correct 10 ms 8300 KB Output is correct
13 Correct 7 ms 8300 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 7 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 6 ms 8300 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 7 ms 8300 KB Output is correct
11 Correct 7 ms 8192 KB Output is correct
12 Correct 10 ms 8300 KB Output is correct
13 Correct 7 ms 8300 KB Output is correct
14 Correct 57 ms 14948 KB Output is correct
15 Correct 33 ms 12652 KB Output is correct
16 Correct 54 ms 15076 KB Output is correct
17 Correct 31 ms 12260 KB Output is correct