Submission #1390806
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];
int mutual(int n, const string &s, const string &t) {
// cerr << "call(mutual):" << n << " " << s << " " << t << endl;
if (n <= 2) {
return 0;
}
if (s.substr(0, t.length()) == t) {
int sub = mutual(n - 1, t, s.substr(t.length()));
if (sub >= 0) {
return 2 * sub;
}
}
if (s.substr(s.length() - t.length()) == t) {
int sub = mutual(n - 1, t, s.substr(0, s.length() - t.length()));
if (sub >= 0) {
return 2 * sub + 1;
}
}
return -1;
}
// if not found, return -1.
int rec(int k) {
if(k == 1) {
return s.substr(0, fib[k]) == "b" ? 0 : -1;
}
if(k == 2) {
return s.substr(0, fib[k]) == "a" ? 0 : -1;
}
// [k-3] [k-2] [k-2] ?
int f3 = fib[k-3];
int f2 = fib[k-2];
if(s.substr(f3,f2) == s.substr(f3 + f2, f2)) {
int sub = mutual(k - 2, s.substr(f3, f2), s.substr(0, f3));
if(sub >= 0) {
return sub * 4 + 2;
}
}
// [k-2] [k-3] [k-2] ?
if(s.substr(0, f2) == s.substr(f3 + f2, f2)) {
int sub = mutual(k - 2, s.substr(0, f2), s.substr(f2, f3));
if(sub >= 0)
return sub * 4;
}
// [k - 2] [k - 2] [k - 3] ?
if(s.substr(0, f2) == s.substr(f2, f2)) {
int sub = mutual(k - 2, s.substr(0, f2), s.substr(2 * f2, f3));
if(sub >= 0)
return sub * 4 + 1;
}
return -1;
}
void enumerate_few(void) {
vector<vector<string> > dp(10);
dp[0] = vector<string>(1, "b");
dp[1] = vector<string>(1, "a");
REP(i, 2, 6) {
dp[i] = vector<string>(1 << (i - 1), "");
REP(k, 0, 1 << (i - 1)) {
if (k % 2 == 0) {
dp[i][k] = dp[i - 1][k / 2] + dp[i - 2][k / 4];
} else {
dp[i][k] = dp[i - 2][k / 4] + dp[i - 1][k / 2];
}
}
REP(k, 0, 1 << (i - 1)) {
cerr << "dp[" << i << "][" << k << "]=" << dp[i][k] << endl;
}
}
}
int main(void){
cin>>s;
fib_init();
//enumerate_few();
if(s == "a") {
cout << "2 0" << endl;
return 0;
}
if(s == "b") {
cout << "1 0" << endl;
return 0;
}
int n = -1;
REP(i,0,N) {
if((int) s.length() == fib[i]) {
n=i;
break;
}
}
cout << n << " " << rec(n) << endl;
}
Submission Info
Submission Time |
|
Task |
E - ab文字列 |
User |
kobae964 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2604 Byte |
Status |
WA |
Exec Time |
2 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
WA |
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 |