Source code for submission s1103

Go to diff to previous submission

fm.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11. #include <utility>
  12.  
  13. using namespace std;
  14.  
  15.  
  16. vector<vector<char> > mapka;
  17. vector<int> intervalac;
  18.  
  19. int AR,AC,TR,TC, mocnina;
  20.  
  21. int spusti(int vrchol, pair<int,int> LH, pair<int,int> PD){
  22. if(PD.first-LH.first==1) {
  23. if(mapka[LH.first][LH.second]=='X') {
  24. intervalac[vrchol] = 1;
  25. return 1;
  26.  
  27. }
  28. else return 0;
  29. }
  30.  
  31. intervalac[vrchol] = spusti(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2))
  32. + spusti(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2))
  33. + spusti(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second))
  34. + spusti(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD);
  35.  
  36. return intervalac[vrchol];
  37. }
  38.  
  39. int pocet(int vrchol, pair<int,int> LH, pair<int,int> PD, pair<int,int> HlaLH, pair<int,int> HlaPD){
  40. if(HlaLH.first <= LH.first && HlaLH.second <= LH.second && HlaPD.first >= PD.first && HlaPD.second >= PD.second)
  41. return intervalac[vrchol];
  42. else if (HlaLH.first >= PD.first || HlaLH.second >= PD.second || HlaPD.first <= LH.first || HlaPD.second <= LH.second) return 0;
  43. else {
  44. int vrat = 0;
  45. vrat = pocet(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), HlaLH, HlaPD);
  46. if(vrat) return 1;
  47. 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);
  48. if(vrat) return 1;
  49. 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);
  50. if(vrat) return 1;
  51. vrat = pocet(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD, HlaLH, HlaPD);
  52. if(vrat) return 1;
  53. else
  54. return 0;
  55. }
  56.  
  57. }
  58.  
  59. int skus(int x, int y){
  60. int vys = 0;
  61.  
  62. for(int i = x; i + TR < mocnina; i += TR){
  63. for(int j = y; j + TC < mocnina; j += TC){
  64.  
  65. //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;
  66.  
  67. if(pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC)) > 0) vys++;
  68. }
  69. }
  70.  
  71. return vys;
  72. }
  73.  
  74.  
  75. int main(){
  76. while(scanf("%d%d%d%d",&AR,&AC,&TR,&TC)!=EOF){
  77.  
  78.  
  79. mapka.clear();
  80. intervalac.clear();
  81.  
  82. mocnina = 1;
  83. while(mocnina < TR+AR+TR) mocnina *= 2;
  84.  
  85. while(mocnina < TC+AC+TC) mocnina *= 2;
  86.  
  87. mapka.resize(mocnina, vector<char> (mocnina,'.'));
  88.  
  89. intervalac.resize(mocnina * mocnina * 2, 0);
  90.  
  91. int pocetK=0;
  92. string riadok;
  93. for(int i = 0; i < AR; i++){
  94. cin>>riadok;
  95. for(int j = 0; j < riadok.size(); j++){
  96. mapka[i + TR ][j + TC ] = riadok[j];
  97. if(riadok[j] == 'X') pocetK++;
  98. }
  99. }
  100.  
  101. if(TR == 1 && TC == 1) {cout<<pocetK<<endl; continue;}
  102.  
  103. spusti(0,make_pair(0,0), make_pair(mocnina, mocnina));
  104.  
  105. /* for(int i = 0; i < mocnina; i++){
  106.   for(int j=0; j< mocnina; j++){
  107. cout<<mapka[i][j];
  108.  
  109.   }
  110.   cout<<endl;
  111.   }
  112.  
  113.   for(int i =0; i< mocnina * mocnina ; i++){
  114.   cout<<intervalac[i]<<" ";
  115.   }*/
  116.  
  117. int najmensie = 100000000;
  118.  
  119.  
  120. if(AC*AR <= 3500){
  121. for(int i = 0; i < TR; i++){
  122. for(int j = 0; j < TC; j++){
  123. najmensie = min(skus(i,j), najmensie);
  124. }
  125.  
  126. }
  127. }
  128. else{
  129. for(int i = 0; i < TR; i+=20){
  130. for(int j = 0; j < TC; j+=10){
  131. najmensie = min(skus(i,j), najmensie);
  132. }
  133.  
  134. }
  135. }
  136.  
  137. cout<<najmensie<<endl;
  138.  
  139. }
  140.  
  141. }

Diff to submission s1102

fm.cpp

--- c5.s1102.cteam090.fm.cpp.0.fm.cpp
+++ c5.s1103.cteam090.fm.cpp.0.fm.cpp
@@ -118,5 +118,5 @@
     
     
-    if(AC*AR <= 2500){
+    if(AC*AR <= 3500){
     for(int i = 0; i < TR; i++){
       for(int j = 0; j < TC; j++){
@@ -127,5 +127,5 @@
     }
     else{
-      for(int i = 0; i < TR; i+=10){
+      for(int i = 0; i < TR; i+=20){
         for(int j = 0; j < TC; j+=10){
           najmensie = min(skus(i,j), najmensie);