Code Formula 2014 本選

Submission #1513311

Source codeソースコード

#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<58;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

string s;

int main(){
	cin>>s;
	int S=s.size();
	if(S==1){
		if(s=="a") cout<<2<<' '<<0<<endl;
		else cout<<1<<' '<<0<<endl;
		return 0;
	}
	vi F(30);
	F[1]=1;
	int I=2;
	while((F[I]=F[I-1]+F[I-2])!=S) I++;
	cout<<I<<' ';
	ull H=0;
	for(int i=0;i<S;i++) H=H*mod+s[i];
	vector<ull> Mod(I);
	vector<vector<ull> > dp(I);
	Mod[0]=mod;
	Mod[1]=mod;
	for(int i=2;i<I;i++) Mod[i]=Mod[i-1]*Mod[i-2];
	int two=1;
	for(int i=0;i<I;i++){
		dp[i]=vector<ull>(two);
		if(i) two*=2;
	}
	dp[0][0]='b';
	dp[1][0]='a';
	for(int i=2;i<I;i++) for(int j=0;j<dp[i].size();j++){
		if(j%2==0) dp[i][j]=dp[i-1][j/2]*Mod[i-2]+dp[i-2][j/4];
		else dp[i][j]=dp[i-2][j/4]*Mod[i-1]+dp[i-1][j/2];
		if(i==I-1&&dp[i][j]==H){
			cout<<j<<endl;
			break;
		}
	}
}

Submission

Task問題 E - ab文字列
User nameユーザ名 MAK
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1872 Byte
File nameファイル名
Exec time実行時間 10 ms
Memory usageメモリ使用量 16640 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 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 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 384 KB
test_16_16383.txt AC 1 ms 512 KB
test_18_65535.txt AC 2 ms 1280 KB
test_1_0.txt AC 1 ms 256 KB
test_22_0.txt AC 9 ms 16640 KB
test_22_1048575.txt AC 10 ms 16640 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