Submission #993679


Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
vector<string> bd;
const in mdl=1000000007;
VI rcon,ccon;
VVI bas;
queue<in> rrm,crm;
in totrm=0;
in sm=1;
void rmr(in u){
  in s=0;
  forv(i,bas[u]){
    s+=bas[u][i];
    if(bas[u][i]){
      --ccon[i];
      if(ccon[i]<=1){
	++totrm;
	crm.push(i);
      }
    }
  }
  if(s)
    sm*=2;
  sm%=mdl;
}
void rmc(in u){
  in s=0;
  forv(i,bas){
    s+=bas[i][u];
    if(bas[i][u]){
      --rcon[i];
      if(rcon[i]<=1){
	++totrm;
	rrm.push(i);
      }
    }
  }
  if(s)
    sm*=2;
  sm%=mdl;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in h,w;
  cin>>h>>w;
  bd.resize(h);
  forn(i,h)
    cin>>bd[i];
  if(h%2){
    string s=bd[h/2];
    reverse(all(s));
    if(s!=bd[h/2])
      sm*=2;
  }
  if(w%2){
    string s(h,'a');
    forn(i,h)
      s[i]=bd[i][w/2];
    reverse(all(s));
    bool dif=0;
    forn(i,h)
      if(s[i]!=bd[i][w/2])
	dif=1;
    if(dif)
      sm*=2;
  }
  bas.resize(h/2,VI(w/2));
  rcon.resize(h/2);
  ccon.resize(w/2);
  forn(i,h/2){
    forn(j,w/2){
      string s;
      s.PB(bd[i][j]);
      s.PB(bd[h-1-i][j]);
      s.PB(bd[i][w-1-j]);
      s.PB(bd[h-1-i][w-1-j]);
      sort(all(s));
      in pm=24;
      in csz=1;
      forn(z,4){
	if(z==0 || s[z]!=s[z-1]){
	  for(in zz=1;zz<=csz;++zz)
	    pm/=zz;
	  csz=1;
	  continue;
	}
	++csz;
      }
      for(in zz=1;zz<=csz;++zz)
	pm/=zz;
      if(pm==24){
	++rcon[i];
	++ccon[j];
	bas[i][j]=1;
	pm/=2;
      }
      sm*=pm;
      sm%=mdl;
    }
  }
  forv(i,rcon){
    if(rcon[i]<=1){
      ++totrm;
      rrm.push(i);
    }
  }
  forv(i,ccon){
    if(ccon[i]<=1){
      ++totrm;
      crm.push(i);
    }
  }
  in u;
  while(!rrm.empty() || !crm.empty()){
    if(!rrm.empty()){
      u=rrm.front();
      rrm.pop();
      rmr(u);
    }
    else{
      u=crm.front();
      crm.pop();
      rmc(u);
    }
  }
  in lft=h/2+w/2-totrm-1;
  forn(i,lft)
    sm=sm*2%mdl;
  cout<<sm<<endl;
  return 0;
}

Submission Info

Submission Time
Task I - Reverse Grid
User w4yneb0t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2482 Byte
Status TLE
Exec Time 2144 ms
Memory 818440 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1900
Status
AC × 2
AC × 35
TLE × 2
Set Name Test Cases
sample sample-01.txt, sample-02.txt
all sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 256 KB
01-02.txt TLE 2102 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 256 KB
01-05.txt AC 3 ms 256 KB
01-06.txt AC 3 ms 256 KB
01-07.txt AC 3 ms 256 KB
01-08.txt AC 3 ms 256 KB
01-09.txt AC 3 ms 256 KB
01-10.txt AC 5 ms 384 KB
01-11.txt AC 5 ms 384 KB
01-12.txt AC 5 ms 384 KB
01-13.txt AC 5 ms 384 KB
01-14.txt AC 3 ms 256 KB
01-15.txt AC 3 ms 256 KB
01-16.txt AC 5 ms 384 KB
01-17.txt AC 5 ms 384 KB
01-18.txt AC 5 ms 384 KB
01-19.txt AC 6 ms 384 KB
01-20.txt AC 5 ms 384 KB
01-21.txt AC 5 ms 384 KB
01-22.txt AC 3 ms 256 KB
01-23.txt AC 4 ms 384 KB
01-24.txt AC 5 ms 384 KB
01-25.txt AC 5 ms 384 KB
01-26.txt AC 5 ms 384 KB
01-27.txt AC 3 ms 256 KB
01-28.txt AC 3 ms 256 KB
01-29.txt TLE 2144 ms 818440 KB
01-30.txt AC 3 ms 256 KB
01-31.txt AC 5 ms 384 KB
01-32.txt AC 5 ms 384 KB
01-33.txt AC 6 ms 384 KB
01-34.txt AC 5 ms 384 KB
01-35.txt AC 5 ms 384 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB