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
#include <bits/stdc++.h>
#include "cielib.h"
using namespace std;

int main() {
  int d = podajD();
  int r = podajR();
  
  vector<int> lowerBound(d, 0);
  vector<int> upperBound(d, r);
  vector<int> X(d, (r+1)/2);

  for (;;) {
    bool done = true;
    for (int i = 0; i < d; ++i) {

      if (lowerBound[i] < upperBound[i]) {
        int width = min(lowerBound[i], r-upperBound[i]);
        
        X[i] = lowerBound[i]-width;
        czyCieplo(X.data());
        X[i] = upperBound[i]+width;
        int a1 = czyCieplo(X.data());
        
        if (a1) // [rightmost] < [leftmost]
          lowerBound[i] = lowerBound[i] + (upperBound[i]-lowerBound[i]+1)/2;
        else {        
          X[i] = lowerBound[i]-width;
          int a2 = czyCieplo(X.data());
          if (a2) { // [leftmost] < [rightmost]          
            upperBound[i] = lowerBound[i] + (upperBound[i]-lowerBound[i]-1)/2;

          } else { //equal
            int maxError = 0;
            for (int j = 0; j<d; ++j) {
              if (i==j) continue;
              maxError = max(maxError, abs(X[j] - lowerBound[j]));
              maxError = max(maxError, abs(X[j] - upperBound[j]));
            }
            if (upperBound[i]-lowerBound[i] <= 2*maxError) {              
              int olb = lowerBound[i];
              lowerBound[i] = upperBound[i]-maxError;
              upperBound[i] = olb+maxError;
            } else {
              assert((upperBound[i]-lowerBound[i])%2 == 0);
              lowerBound[i] = upperBound[i] = (upperBound[i]-lowerBound[i])/2;
            }
          }
        }
        //cerr << "X[" << i << "] = " << lowerBound[i] << ":" << upperBound[i] << endl;
      }
      
      X[i] = (lowerBound[i] + upperBound[i] + 1)/2;
      
      if (lowerBound[i] < upperBound[i]) done = false;
    }
    if (done) break;
  }
  
  znalazlem(X.data());
}