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
AC × 19
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