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
Task D - アルファベット探し
User ishikado
Language C++ (G++ 4.6.4)
Score 0
Code Size 3687 Byte
Status MLE
Exec Time 2041 ms
Memory 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