Submission #1390914


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 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;
  }
  if (s == "ab") {
    cout << "3 0" << endl;
    return 0;
  }
  if (s == "ba") {
    cout << "3 1" << 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 100
Code Size 2721 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