Submission #1388117


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
const double EPS=1e-9;

const int N = 24;
const int B = 1 << 23;

string s;

int fib[N];

void fib_init(void) {
	int x = 0;
	int y = 1;
	REP(i,0,N) {
		fib[i] = x;
		int r = x + y;
		x = y;
		y = r;
	}
}

int dp[N][B];

// if not found, return -1.
int rec(int k,int b) {
	int &r = dp[k][b];
	if(r >= -1) return r;
	if(k == 1) {
		return s.substr(b,fib[k]) == "b" ? 0 : -1;
	}
	if(k == 2) {
		return s.substr(b,fib[k]) == "a" ? 0 : -1;
	}
	// [k-3] [k-2] [k-2]
	int f3 = fib[k-3];
	int f2 = fib[k-2];
	if(s.substr(b + f3,f2) == s.substr(b + f3 + f2, f2)) {
		int sub = rec(k-2, b + f3);
		if(sub >= 0)
			return sub * 4 + 1;
	}
	if(s.substr(b ,f2) == s.substr(b + f3 + f2, f2)) {
		int sub = rec(k-2, b + f3);
		if(sub >= 0)
			return sub * 4;
	}
	if(s.substr(b,f2) == s.substr(b + f2, f2)) {
		int sub = rec(k-2, b + f3);
		if(sub >= 0)
			return sub * 4 + 2;
	}
	return -1;
}

int main(void){
	cin>>s;
	fib_init();
	int n;
	if(s == "a") {
		cout << "2 0" << endl;
		return 0;
	}
	if(s == "b") {
		cout << "1 0" << endl;
		return 0;
	}
	REP(i,0,N) {
		if(s.size() == fib[i]) {
			n=i;
			break;
		}
	}
	cout << n << " " << rec(0,n) << endl;
}

Submission Info

Submission Time
Task E - ab文字列
User kobae964
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1426 Byte
Status WA
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 5
WA × 14
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 WA 1 ms 256 KB
sample_02.txt WA 1 ms 256 KB
test_11_511.txt WA 1 ms 256 KB
test_13_2047.txt WA 1 ms 256 KB
test_15_8191.txt WA 1 ms 256 KB
test_16_16383.txt WA 1 ms 256 KB
test_18_65535.txt WA 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 WA 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 WA 1 ms 256 KB
test_4_3.txt AC 1 ms 256 KB
test_5_7.txt WA 1 ms 256 KB
test_6_15.txt WA 1 ms 256 KB
test_8_63.txt WA 1 ms 256 KB