Go to diff to previous submission
#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <set> #include <string> #include <cmath> #include <algorithm> #include <queue> #include <utility> using namespace std; vector<vector<char> > mapka; vector<int> intervalac; int AR,AC,TR,TC, mocnina; int spusti(int vrchol, pair<int,int> LH, pair<int,int> PD){ if(PD.first-LH.first==1) { if(mapka[LH.first][LH.second]=='X') { intervalac[vrchol] = 1; return 1; } else return 0; } intervalac[vrchol] = spusti(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2)) + spusti(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2)) + spusti(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second)) + spusti(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD); return intervalac[vrchol]; } int pocet(int vrchol, pair<int,int> LH, pair<int,int> PD, pair<int,int> HlaLH, pair<int,int> HlaPD){ if(HlaLH.first <= LH.first && HlaLH.second <= LH.second && HlaPD.first >= PD.first && HlaPD.second >= PD.second) return intervalac[vrchol]; else if (HlaLH.first >= PD.first || HlaLH.second >= PD.second || HlaPD.first <= LH.first || HlaPD.second <= LH.second) return 0; else { int vrat = 0; vrat = pocet(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), HlaLH, HlaPD); if(vrat) return 1; vrat = pocet(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2), HlaLH, HlaPD); if(vrat) return 1; vrat = pocet(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second), HlaLH, HlaPD); if(vrat) return 1; vrat = pocet(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD, HlaLH, HlaPD); if(vrat) return 1; else return 0; } } int skus(int x, int y){ int vys = 0; for(int i = x; i + TR < mocnina; i += TR){ for(int j = y; j + TC < mocnina; j += TC){ //cout<<"od: ["<<i<<", "<<j<<"] po ["<<i+TR<<", "<<j+TC<<"] to je "<<pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC))<<endl; if(pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC)) > 0) vys++; } } return vys; } int main(){ while(scanf("%d%d%d%d",&AR,&AC,&TR,&TC)!=EOF){ mapka.clear(); intervalac.clear(); mocnina = 1; while(mocnina < TR+TR+AR+TR+TR) mocnina *= 2; while(mocnina < TC+TC+AC+TC+TC) mocnina *= 2; mapka.resize(mocnina, vector<char> (mocnina,'.')); intervalac.resize(mocnina * mocnina * 2, 0); int pocetK=0; string riadok; for(int i = 0; i < AR; i++){ cin>>riadok; for(int j = 0; j < riadok.size(); j++){ mapka[i + TR * 2][j + TC * 2] = riadok[j]; if(riadok[j] == 'X') pocetK++; } } if(TR == 1 && TC == 1) {cout<<pocetK<<endl; continue;} spusti(0,make_pair(0,0), make_pair(mocnina, mocnina)); /* for(int i = 0; i < mocnina; i++){ for(int j=0; j< mocnina; j++){ cout<<mapka[i][j]; } cout<<endl; } for(int i =0; i< mocnina * mocnina ; i++){ cout<<intervalac[i]<<" "; }*/ int najmensie = 100000000; if(AC*AR <= 1000){ for(int i = 0; i < TR; i++){ for(int j = 0; j < TC; j++){ najmensie = min(skus(i,j), najmensie); } } } else{ for(int i = 0; i < TR; i+=10){ for(int j = 0; j < TC; j+=20){ najmensie = min(skus(i,j), najmensie); } } } cout<<najmensie<<endl; } }
--- c5.s1086.cteam090.fm.cpp.0.fm.cpp +++ c5.s1089.cteam090.fm.cpp.0.fm.cpp @@ -128,5 +128,5 @@ else{ for(int i = 0; i < TR; i+=10){ - for(int j = 0; j < TC; j+=10){ + for(int j = 0; j < TC; j+=20){ najmensie = min(skus(i,j), najmensie); }