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 |
|
|
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 |