oj.uz

Submission #1017419

# Submission time Handle Problem Language Result Execution time Memory
1017419 2024-07-09T07:51:37 Z cnn008 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 104 ms 28776 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif

#define int long long

const int N=1e6+5;
const int mod=1e9+7;
const int base=311;

int n,ans,h[N],pw[N];
string s;
int get(int l, int r){
	return (h[r]-((h[l-1]*pw[r-l+1])%mod)+mod)%mod;
}
void sol(){
	ans=0;
	cin>>s;
	n=(int)s.size();
	s=' '+s;
	for(int i=1; i<=n; i++) h[i]=(h[i-1]*base+s[i]-'a'+1)%mod;
	int l=1,r=n;
	while(l<=r){
		int _l=l,_r=r,f=0;
		while(_l<_r){
			if(get(l,_l++)==get(_r--,r)){
				cebug(s,l,_l,_r,r);
				ans+=2;
				f=1;
				break;
			}
		}
		if(!f){
			ans++;
			break;
		}
		l=_l;
		r=_r;
	}
	cout<<ans<<"\n";
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    pw[0]=1;
	for(int i=1; i<N; i++) pw[i]=(pw[i-1]*base)%mod;
    int tt=1;
    cin>>tt; 
    while(tt--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

Compilation message

palindromic.cpp: In function 'void sol()':
palindromic.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define cebug(...) "Arya"
      |                    ^~~~~~
palindromic.cpp:32:5: note: in expansion of macro 'cebug'
   32 |     cebug(s,l,_l,_r,r);
      |     ^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8284 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 6 ms 8288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8284 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 6 ms 8288 KB Output is correct
6 Correct 7 ms 8064 KB Output is correct
7 Correct 6 ms 8056 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 7 ms 8060 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8284 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 6 ms 8288 KB Output is correct
6 Correct 7 ms 8064 KB Output is correct
7 Correct 6 ms 8056 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 7 ms 8060 KB Output is correct
10 Correct 8 ms 8280 KB Output is correct
11 Correct 7 ms 8284 KB Output is correct
12 Correct 8 ms 8508 KB Output is correct
13 Correct 7 ms 8320 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8284 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 6 ms 8288 KB Output is correct
6 Correct 7 ms 8064 KB Output is correct
7 Correct 6 ms 8056 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 7 ms 8060 KB Output is correct
10 Correct 8 ms 8280 KB Output is correct
11 Correct 7 ms 8284 KB Output is correct
12 Correct 8 ms 8508 KB Output is correct
13 Correct 7 ms 8320 KB Output is correct
14 Correct 104 ms 27720 KB Output is correct
15 Correct 63 ms 23072 KB Output is correct
16 Correct 94 ms 28776 KB Output is correct
17 Correct 59 ms 18516 KB Output is correct