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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include "cielib.h"
#include <math.h>
//#include <iostream>
#include <climits>
#include <algorithm>    // std::max

int czyCieploDoubleQuery(int t[], long long query1, long long query2, int dimension){
	//std::cout << "[czyCieploDoubleQuery] query1=" << query1 << std::endl;
	t[dimension] = query1;
	//std::cout << "t[dimension]=" << t[dimension] << std::endl;
	czyCieplo(t);
	//std::cout << "[czyCieploDoubleQuery] query2=" << query2 << std::endl;
	t[dimension] = query2;
	//std::cout << "t[dimension]=" << t[dimension] << std::endl;
	return czyCieplo(t);
}

void find_top_statistics(int d, int lower[], int upper[], int & topindex,
		int & secondtopindex, int & difftop, int & diffsecondtop){
	topindex = -1;
	secondtopindex = -1;
	difftop = -1;
	diffsecondtop = -1;
	for(int i=0; i<d; i++){
		//std::cout << "[find_top_statistics] i=" << i << " topindex=" << topindex << "secondtopindex=" << secondtopindex << "difftop="<< difftop << "diffsecondtop=" << diffsecondtop << std::endl;
		int currdiff = upper[i]-lower[i];
		if(currdiff > difftop){
			diffsecondtop = difftop;
			secondtopindex = topindex;
			difftop = currdiff;
			topindex = i;
		}
		else if(currdiff > diffsecondtop){
			diffsecondtop = currdiff;
			secondtopindex = i;
		}
	}
}

int main() {
	int d = podajD();
	int k = podajK();
	long long r = podajR();

	int t[d];
	int lower[d];
	int upper[d];
	for(int i = 0; i < d; ++i) {
		lower[i] = 0;
		upper[i] = r;
		t[i] = r/2;
	}

	int topindex, secondtopindex, difftop, diffsecondtop;
	while(true) {
		//find index with the highest
		find_top_statistics(d, lower, upper, topindex, secondtopindex, difftop, diffsecondtop);
		//std::cout << "topindex=" << topindex << " secondtopindex=" << secondtopindex
		//		<< " difftop=" << difftop << " diffsecondtop=" << diffsecondtop << std::endl;
		//std::cout << "lower[topindex]=" << lower[topindex] <<
		//		"upper[topindex]=" << upper[topindex] << std::endl;
		if(difftop==0){
			break;
		}
		if(difftop <= 2) {
			//std::cout << "difftop <= 2" << std::endl;
			//should I check that there is no dimension with just 2? Otherwise, expand those dimensions.
			for(int i=0; i<d; i++){
				if (upper[i]-lower[i] == 1){
					//std::cout << "artificially increasing upper for a dimension with diff! i=" << i << std::endl;
					upper[i]++;
				}
				if(i != topindex && upper[i]-lower[i] > 0){
					t[i] = lower[i]+1;
				}
			}
			if(czyCieploDoubleQuery(t, lower[topindex], lower[topindex]+1, topindex)){
				if(czyCieploDoubleQuery(t, lower[topindex], upper[topindex], topindex)){
					lower[topindex]=upper[topindex];
					t[topindex]=upper[topindex];
				}
				else{
					upper[topindex]=lower[topindex]+1;
					t[topindex]=lower[topindex]+1;
					lower[topindex]=lower[topindex]+1;
				}
			}
			else{
				if(czyCieploDoubleQuery(t, upper[topindex], lower[topindex], topindex)){
					upper[topindex]=lower[topindex];
					t[topindex]=lower[topindex];
				}
				else{
					upper[topindex]=lower[topindex]+1;
					t[topindex]=lower[topindex]+1;
					lower[topindex]=lower[topindex]+1;
				}
			}
		}
		else {
			int q1, q2, bias;
			if(d==1){
				bias=ceil(difftop/2);
			}
			else{
				bias = std::min(floor(diffsecondtop/2),
							ceil(diffsecondtop/2));
			}
			q1 = lower[topindex];
			q2 = upper[topindex];
			//std::cout << "q1=" << q1 << std::endl;
			//std::cout << "q2=" << q2 << std::endl;
			if(czyCieploDoubleQuery(t, q1, q2, topindex)){
				lower[topindex] += bias;
			}
			else{
				upper[topindex] -= bias;
			}
			t[topindex] = (upper[topindex] + lower[topindex])/2;
			//std::cout << "new values for topindex=" << topindex << " lower[topindex]=" << lower[topindex] <<
			//		" upper[topindex]=" << upper[topindex] << " t[topindex]=" << t[topindex] << std::endl;
		}
	}
	znalazlem(t);
}