1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <list>
#include "cielib.h"

int main() {
  int d = podajD();
  int k = podajK();
  int r = podajR();
  int *pozycja = new int[d + 5];
	
  std::list< int > currLongIntervalNos;
  std::list< std::pair< int, int> > currLongIntervals; // range [first, second]
  std::list< int > nextLongIntervalNos;
  std::list< std::pair< int, int> > nextLongIntervals; // range [first, second]
  int currLen = r + 1;
  for(int i = 0; i < d; i++) {
    currLongIntervalNos.push_back(i);
    currLongIntervals.push_back(std::make_pair(0, r));
    pozycja[i] = r / 2;
  }
   
  std::list< int > twosIntervalNos;
  std::list< int > twosIntervals; // range [int, int+1]

  while(!currLongIntervalNos.empty()) {
    nextLongIntervalNos.clear();
    nextLongIntervals.clear();
                  
    auto numsit = currLongIntervalNos.begin();
    auto rangsit = currLongIntervals.begin();
    while(numsit != currLongIntervalNos.end()) {
      int dim = *numsit;
      int b = rangsit->first;
      int e = rangsit->second;
      pozycja[dim] = b;
      czyCieplo(pozycja);
      pozycja[dim] = e;
      int newb, newe;
      if(czyCieplo(pozycja)) {
        // second half
        newb = (b + e) / 2 + 1;
        newe = e;
      } else {
        pozycja[dim] = b;
        if(czyCieplo(pozycja)) {
          // first half
          newb = b;
          newe = (currLen % 2 == 0) ? (b + e) / 2 : (b + e) / 2 - 1;
        } else {
          // middle
          newb = (b + e) / 2;
          newe = (currLen % 2 == 0) ? (b + e) / 2 + 1 : (b + e) / 2;
        }
      }
              
      int lenBE = newe - newb + 1;
      if(lenBE == 1) {
        pozycja[dim] = newb;
      } else if(lenBE == 2) {
        twosIntervalNos.push_back(dim);
        twosIntervals.push_back(newb);
        pozycja[dim] = newb;
      } else {
        nextLongIntervalNos.push_back(dim);
        nextLongIntervals.push_back(std::make_pair(newb, newe));
        pozycja[dim] = (newb + newe) / 2;
      }
      
      numsit++,
      rangsit++;
    }

    currLen /= 2;
    std::swap(nextLongIntervalNos, currLongIntervalNos);
    std::swap(nextLongIntervals, currLongIntervals);
  }

  auto numsit = twosIntervalNos.begin();
  auto rangbegit = twosIntervals.begin();
  while(numsit != twosIntervalNos.end()) {
    int dim = *numsit; 
    int b = *rangbegit;
    int firstPos = (b + 2 <= r) ? b + 2 : b - 1;
    int secondPos = (b + 2 <= r) ? b : b + 1;
    pozycja[dim] = firstPos;
    czyCieplo(pozycja);
    pozycja[dim] = secondPos;
    if(czyCieplo(pozycja) == false) {
      pozycja[dim] = (firstPos + secondPos) / 2;
    }
    
    numsit++;
    rangbegit++;
  }

  znalazlem(pozycja);
}