Submission #5122113
Source Code Expand
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define llong long long
using namespace std;
vector<int> fib(25, -1);
int calc_Fib(int n){
if(fib[n] != -1)return fib[n];
return calc_Fib(n-1) + calc_Fib(n-2);
}
vector<int> g(25,-1);
vector<string> d(25);
int calc(const int n, const string &str, const size_t l, const size_t r){
if(g[n] != -1) return g[n];
// cerr << n << endl;
assert(n >= 3);
// cerr << n << ": " << l << "," << r << endl;
if(n == 3){
if(str[l] == 'b') g[3] = 1;
else g[3] = 0;
return g[3];
}
bool flag1 = true, flag2 = true;
if(g[n-2] != -1 && d[n-2] != str.substr(l,fib[n-2])){
flag1 = false;
flag2 = false;
}
for(int i = 0; i < fib[n-2]; i++){
if(str[l+i] != str[l+fib[n-2]+i] ){
flag1 = false;
}
if(str[l+i] != str[l+fib[n-1]+i]){
flag2 = false;
}
}
if(flag1 || flag2){
g[n-2] = calc(n-2, str, l, l+fib[n-2]);
g[n-1] = calc(n-1, str, l+fib[n-2], r);
d[n-2] = str.substr(l, fib[n-2]);
d[n-1] = str.substr(l+fib[n-2], fib[n-1]);
return 1 + g[n-1]*2;
}
else{
g[n-2] = calc(n-2, str, l+fib[n-1], r);
g[n-1] = calc(n-1, str, l, l+fib[n-1]);
d[n-2] = str.substr(l+fib[n-1], fib[n-2]);
d[n-1] = str.substr(l, fib[n-1]);
return g[n-1]*2;
}
}
signed main(){
fib[1] = 1; fib[2] = 1;
for(int i = 3; i < 25; i++)fib[i] = calc_Fib(i);
g[2] = 0;
g[1] = 0;
d[1] = "b"; d[2] = "a";
string s; cin >> s;
if(s == "b"){
cout << "1 0" << endl;
return 0;
}
int n;
for(int i = 2; i < 25; i++){
if(fib[i] == (int)s.size()){
n = i;
break;
}
}
cout << n << " " << calc(n, s, 0, s.size()) << endl;
// for(int i = 1; i < 7; i++)cerr << g[i] << " ";
// cerr << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - ab文字列 |
User |
rsy3244 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1770 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
sample_01.txt, sample_02.txt, test_11_511.txt, test_13_2047.txt, test_15_8191.txt, test_16_16383.txt, test_18_65535.txt, test_1_0.txt, test_22_0.txt, test_22_1048575.txt, test_2_0.txt, test_3_0.txt, test_3_1.txt, test_4_3.txt, test_5_7.txt, test_6_15.txt, test_8_63.txt, sample_01.txt, sample_02.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
test_11_511.txt |
AC |
1 ms |
256 KB |
test_13_2047.txt |
AC |
1 ms |
256 KB |
test_15_8191.txt |
AC |
1 ms |
256 KB |
test_16_16383.txt |
AC |
1 ms |
256 KB |
test_18_65535.txt |
AC |
1 ms |
256 KB |
test_1_0.txt |
AC |
1 ms |
256 KB |
test_22_0.txt |
AC |
2 ms |
256 KB |
test_22_1048575.txt |
AC |
2 ms |
256 KB |
test_2_0.txt |
AC |
1 ms |
256 KB |
test_3_0.txt |
AC |
1 ms |
256 KB |
test_3_1.txt |
AC |
1 ms |
256 KB |
test_4_3.txt |
AC |
1 ms |
256 KB |
test_5_7.txt |
AC |
1 ms |
256 KB |
test_6_15.txt |
AC |
1 ms |
256 KB |
test_8_63.txt |
AC |
1 ms |
256 KB |