Contest Duration: - (local time) (90 minutes) Back to Home

Submission #34340

Source Code Expand

Copy
```#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

char af[8][8]={
".......",
"...o...",
"..o.o..",
".o...o.",
".ooooo.",
".o...o.",
"......."
};
char bf[8][8]={
".......",
".oooo..",
".o...o.",
".oooo..",
".o...o.",
".oooo..",
"......."
};
char cf[8][8]={
".......",
"..ooo..",
".o...o.",
".o.....",
".o...o.",
"..ooo..",
"......."
};

typedef long long ll;

const ll P=1000000007;
const ll N=1010;
int H,W;
string field[1001];
ll hashs[1001][1001];

ll p[N];
// rolling hashを計算
void calcRollingHash(string s,int pos){
int n=s.size();
p[0]=1;
// P**iを計算
for(int i=1;i<n+5;i++)p[i]=p[i-1]*P;
hashs[pos][0]=0;
//aa[0]=0;
// hash値を計算
for(int i=1;i<=n;i++)
hashs[pos][i]=hashs[pos][i-1]*P+s[i-1];
}
// 文字列の先頭位置を終端位置を指定し、ハッシュ値を取り出す
inline ll hh(int x,int y,int pos){
return hashs[pos][y+1]-hashs[pos][x]*p[y-x+1];
}

ll vals[1001][1001];
int check(int alpha,vector<string> vs){
int cnt=0;
for(int i=0;i<(int)vs.size();i++){
vals[i][0]=0;
int n=vs[i].size();
for(int j=1;j<=n;j++)
vals[i][j]=vals[i][j-1]*P+vs[i][j-1];
}
for(int i=0;i<=H-(int)vs.size();i++){
for(int j=0;j<=W-(int)vs[0].size();j++){
bool ok=true;
for(int k=0;k<(int)vs.size();k++){
if(hh(j,j+vs[0].size()-1,i+k)!=
vals[k][vs[0].size()]-vals[k][0]*p[vs[0].size()]){
ok=false;
break;
}
}
if(ok)cnt++;
}
}
return cnt;
}

vector<string> rolling(vector<string> fld){
vector<string> nfld=fld;
for(int i=0;i<fld.size();i++)
for(int j=0;j<fld[0].size();j++)
nfld[i][j]=fld[fld[0].size()-1-j][i];
// for(int i=0;i<nfld.size();i++)
//   cout<<nfld[i]<<endl;
return nfld;
}

int main(){
cin>>H>>W;
for(int i=0;i<H;i++){
cin>>field[i];
calcRollingHash(field[i],i);
}
int suma=0;
int sumb=0;
int sumc=0;
{
vector<vector<string> > vvs;
for(int times=1;times*7<=min(H,W);times++){
vector<string> vs;
for(int i=0;i<7;i++){
for(int k=0;k<times;k++){
string s;
for(int j=0;j<7;j++)
for(int l=0;l<times;l++)
s+=af[i][j];
vs.push_back(s);
}
}
vvs.push_back(vs);
}
for(int j=0;j<4;j++){
for(int i=0;i<(int)vvs.size();i++){
suma+=check(0,vvs[i]);
vvs[i]=rolling(vvs[i]);
}
}
}
{
vector<vector<string> > vvs;
for(int times=1;times*7<=min(H,W);times++){
vector<string> vs;
for(int i=0;i<7;i++){
for(int k=0;k<times;k++){
string s;
for(int j=0;j<7;j++)
for(int l=0;l<times;l++)
s+=bf[i][j];
vs.push_back(s);
}
}
vvs.push_back(vs);
}
for(int j=0;j<4;j++){
for(int i=0;i<(int)vvs.size();i++){
sumb+=check(0,vvs[i]);
vvs[i]=rolling(vvs[i]);
}
}
// for(int i=0;i<(int)vvs.size();i++)
//   sumb+=check(0,vvs[i]);
}
{
vector<vector<string> > vvs;
for(int times=1;times*7<=min(H,W);times++){
vector<string> vs;
for(int i=0;i<7;i++){
for(int k=0;k<times;k++){
string s;
for(int j=0;j<7;j++)
for(int l=0;l<times;l++)
s+=cf[i][j];
vs.push_back(s);
}
}
vvs.push_back(vs);
}
for(int j=0;j<4;j++){
for(int i=0;i<(int)vvs.size();i++){
sumc+=check(0,vvs[i]);
vvs[i]=rolling(vvs[i]);
}
}
// for(int i=0;i<(int)vvs.size();i++)
//   sumc+=check(0,vvs[i]);
}
cout<<suma<<" "<<sumb<<" "<<sumc<<endl;
return 0;
}
```

#### Submission Info

Submission Time 2012-07-21 21:39:13+0900 D - アルファベット探し ishikado C++ (G++ 4.6.4) 0 3687 Byte MLE 2041 ms 81920 KB

#### Judge Result

Set Name All
Score / Max Score 0 / 100
Status
 AC × 32 TLE × 23 MLE × 2 RE × 1
Set Name Test Cases
All 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rndsmall_00.txt, 01_rndsmall_01.txt, 01_rndsmall_02.txt, 01_rndsmall_03.txt, 01_rndsmall_04.txt, 01_rndsmall_05.txt, 01_rndsmall_06.txt, 01_rndsmall_07.txt, 01_rndsmall_08.txt, 01_rndsmall_09.txt, 01_rndsmall_10.txt, 01_rndsmall_11.txt, 01_rndsmall_12.txt, 01_rndsmall_13.txt, 01_rndsmall_14.txt, 01_rndsmall_15.txt, 01_rndsmall_16.txt, 01_rndsmall_17.txt, 01_rndsmall_18.txt, 01_rndsmall_19.txt, 02_rndmax_00.txt, 02_rndmax_01.txt, 02_rndmax_02.txt, 02_rndmax_03.txt, 02_rndmax_04.txt, 02_rndmax_05.txt, 02_rndmax_06.txt, 02_rndmax_07.txt, 02_rndmax_08.txt, 02_rndmax_09.txt, 02_rndmax_10.txt, 02_rndmax_11.txt, 02_rndmax_12.txt, 02_rndmax_13.txt, 02_rndmax_14.txt, 02_rndmax_15.txt, 02_rndmax_16.txt, 02_rndmax_17.txt, 02_rndmax_18.txt, 02_rndmax_19.txt, 03_rnd_00.txt, 03_rnd_01.txt, 03_rnd_02.txt, 03_rnd_03.txt, 03_rnd_04.txt, 03_rnd_05.txt, 03_rnd_06.txt, 03_rnd_07.txt, 03_rnd_08.txt, 03_rnd_09.txt, 04_empty_00.txt, 05_maxret_00.txt
Case Name Status Exec Time Memory
00_min.txt AC 41 ms 784 KB
00_sample_01.txt AC 22 ms 912 KB
00_sample_02.txt AC 23 ms 904 KB
00_sample_03.txt AC 23 ms 912 KB
00_sample_04.txt AC 23 ms 784 KB
00_sample_05.txt AC 25 ms 1176 KB
01_rndsmall_00.txt AC 42 ms 2040 KB
01_rndsmall_01.txt AC 44 ms 2048 KB
01_rndsmall_02.txt AC 41 ms 1916 KB
01_rndsmall_03.txt AC 41 ms 2052 KB
01_rndsmall_04.txt AC 42 ms 2048 KB
01_rndsmall_05.txt AC 41 ms 1920 KB
01_rndsmall_06.txt AC 42 ms 1924 KB
01_rndsmall_07.txt AC 45 ms 2016 KB
01_rndsmall_08.txt AC 42 ms 1948 KB
01_rndsmall_09.txt AC 42 ms 2016 KB
01_rndsmall_10.txt AC 41 ms 2044 KB
01_rndsmall_11.txt AC 43 ms 2040 KB
01_rndsmall_12.txt AC 41 ms 1908 KB
01_rndsmall_13.txt AC 40 ms 2036 KB
01_rndsmall_14.txt AC 41 ms 2036 KB
01_rndsmall_15.txt AC 41 ms 2040 KB
01_rndsmall_16.txt AC 44 ms 2040 KB
01_rndsmall_17.txt AC 41 ms 2044 KB
01_rndsmall_18.txt AC 45 ms 2040 KB
01_rndsmall_19.txt AC 42 ms 2048 KB
02_rndmax_00.txt TLE 2039 ms 81788 KB
02_rndmax_01.txt TLE 2039 ms 81916 KB
02_rndmax_02.txt TLE 2041 ms 81912 KB
02_rndmax_03.txt TLE 2041 ms 81908 KB
02_rndmax_04.txt TLE 2039 ms 81920 KB
02_rndmax_05.txt TLE 2038 ms 81916 KB
02_rndmax_06.txt TLE 2039 ms 77176 KB
02_rndmax_07.txt TLE 2040 ms 76400 KB
02_rndmax_08.txt TLE 2039 ms 81912 KB
02_rndmax_09.txt TLE 2040 ms 80768 KB
02_rndmax_10.txt TLE 2041 ms 79992 KB
02_rndmax_11.txt TLE 2041 ms 81916 KB
02_rndmax_12.txt TLE 2039 ms 81908 KB
02_rndmax_13.txt MLE 0 ms 77252 KB
02_rndmax_14.txt TLE 2040 ms 78192 KB
02_rndmax_15.txt TLE 2041 ms 81916 KB
02_rndmax_16.txt TLE 2038 ms 81148 KB
02_rndmax_17.txt TLE 2038 ms 81012 KB
02_rndmax_18.txt MLE 0 ms 78852 KB
02_rndmax_19.txt TLE 2041 ms 81908 KB
03_rnd_00.txt AC 29 ms 1272 KB
03_rnd_01.txt AC 1119 ms 9740 KB
03_rnd_02.txt AC 422 ms 5620 KB
03_rnd_03.txt TLE 2032 ms 17376 KB
03_rnd_04.txt AC 1276 ms 7736 KB
03_rnd_05.txt AC 123 ms 2420 KB
03_rnd_06.txt TLE 2031 ms 27004 KB
03_rnd_07.txt AC 311 ms 4860 KB
03_rnd_08.txt TLE 2033 ms 24700 KB
03_rnd_09.txt RE 0 ms 24184 KB
04_empty_00.txt TLE 2040 ms 75508 KB
05_maxret_00.txt TLE 2039 ms 81916 KB