Code Formula 2014 本選

Submission #1388117

Source codeソースコード

#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

Task問題 E - ab文字列
User nameユーザ名 こば@チーム戦の時は別垢を作れ!
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1426 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt WA
sample_02.txt WA
test_11_511.txt WA
test_13_2047.txt WA
test_15_8191.txt WA
test_16_16383.txt WA
test_18_65535.txt WA
test_1_0.txt AC 1 ms 256 KB
test_22_0.txt AC 2 ms 256 KB
test_22_1048575.txt WA
test_2_0.txt AC 1 ms 256 KB
test_3_0.txt AC 1 ms 256 KB
test_3_1.txt WA
test_4_3.txt AC 1 ms 256 KB
test_5_7.txt WA
test_6_15.txt WA
test_8_63.txt WA