AtCoder Beginner Contest 032

Submission #608838

Source codeソースコード

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const int B=999999937;
const int P=1000000007;

void gen_hash(const string &s,vector<long long> &hash){
	long long c=0;
	for(int i=0;i<s.size();i++){
		c=(c*B+s[i])%P;
		hash[i]=c;
	}
}
long long pow_binary_mod(long long x,long long y,long long mod){
	long long z=1;
	for(;y;y>>=1){
		if((y&1)!=0)z=z*x%mod;
		x=x*x%mod;
	}
	return z;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	set<long long>se;
	string s;
	int lq;
	cin>>s>>lq;
	int ls=s.size();
	vector<long long> v(ls);
	gen_hash(s,v);
	long long Brev=pow_binary_mod(B,lq,P);
	int i=lq-1;
	for(;i<ls;i++)se.insert(((v[i]-(i>=lq?v[i-lq]:0)*Brev)%P+P)%P);
	printf("%d\n",se.size());
}

Submission

Task問題 B - 高橋君とパスワード
User nameユーザ名 cf16::002_ciel
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 AC
Score得点 100
Source lengthソースコード長 804 Byte
File nameファイル名
Exec time実行時間 36 ms
Memory usageメモリ使用量 1028 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:25: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::set<long long int>::size_type {aka long unsigned int}’ [-Wformat=]
printf("%d\n",se.size());
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt
All 100 / 100 subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample_01.txt AC 36 ms 888 KB
subtask0_sample_02.txt AC 31 ms 944 KB
subtask0_sample_03.txt AC 29 ms 952 KB
subtask1_01.txt AC 29 ms 992 KB
subtask1_02.txt AC 32 ms 884 KB
subtask1_03.txt AC 30 ms 948 KB
subtask1_04.txt AC 31 ms 948 KB
subtask1_05.txt AC 30 ms 952 KB
subtask1_06.txt AC 30 ms 976 KB
subtask1_07.txt AC 28 ms 988 KB
subtask1_08.txt AC 30 ms 956 KB
subtask1_09.txt AC 28 ms 956 KB
subtask1_10.txt AC 32 ms 892 KB
subtask1_11.txt AC 29 ms 896 KB
subtask1_12.txt AC 29 ms 1020 KB
subtask1_13.txt AC 27 ms 964 KB
subtask1_14.txt AC 29 ms 964 KB
subtask1_15.txt AC 29 ms 960 KB
subtask1_16.txt AC 29 ms 856 KB
subtask1_17.txt AC 30 ms 976 KB
subtask1_18.txt AC 28 ms 980 KB
subtask1_19.txt AC 28 ms 960 KB
subtask1_20.txt AC 29 ms 956 KB
subtask1_21.txt AC 29 ms 884 KB
subtask1_22.txt AC 29 ms 1028 KB
subtask1_23.txt AC 29 ms 1028 KB