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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include "cielib.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	srand(2137);
	int d = podajD();
	int r = podajR();
	int t[d];
	int as[d], bs[d];
	for (int i = 0; i < d; i++) t[i] = r / 2;
	for (int i = 0; i < d; i++) {
		as[i] = 0;
		bs[i] = r;
	}
	vector<int> is;
	for (int i = 0; i < d; i++) is.push_back(i);
	//random_shuffle(is.begin(), is.end());
	while (!is.empty()) {
		int i = is.back();
		is.pop_back();
		bool lewy_spadek = false, prawy_spadek = false;
		t[i] = 0;
		czyCieplo(t);
		t[i] = 1;
		if (czyCieplo(t) == 1) {
			// cout << i + 1 << " = LEWY SPADEK" << endl;
			lewy_spadek = true;
 		}
 		t[i] = r;
 		czyCieplo(t);
 		t[i] = r - 1;
 		if (czyCieplo(t) == 1) {
 			// cout << i + 1 << " = PRAWY SPADEK" << endl;
 			prawy_spadek = true;
 		}
 		t[i] = r / 2;
 		if (lewy_spadek && prawy_spadek) {
 			t[i] = 0;
 			czyCieplo(t);
 			t[i] = r;
 			int a, b;
 			int koniec;
 			bool tryb;
 			if (czyCieplo(t) == 1) { // f(0) > f(r)
 				a = max(0, as[i]);
 				b = min(r - 1, bs[i]);
 				koniec = r; // wyszukany element = f(r)
 				tryb = true;
 			} else {
 				// f(0) <= f(r)
 				a = max(1, as[i]);
 				b = min(r, bs[i]);
 				koniec = 0; // wyszukany element = f(0)
 				tryb = false;
 			}
 			while (a <= b) {
 				int mid = (a + b) / 2;
 				t[i] = mid;
 				czyCieplo(t);
 				t[i] = koniec;
 				if (czyCieplo(t) == 1) { // f(mid) > f(koniec)
 					if (tryb) a = mid + 1;
 					else b = mid - 1;
 				} else {
 					// t[i] = mid;
 					// if (czyCieplo(t) == 1) { // f(koniec) > f(mid)
 						if (tryb) b = mid - 1;
 						else a = mid + 1;
 					// } else { // f(koniec) == f(mid)
 					// 	t[i] = (koniec + mid) / 2;
 					// 	cout << "ZNALEZIONO " << i + 1 << " = " << t[i] << endl;
 					// 	break;
 					// }
 				}
 			}
 			t[i] = (koniec + b + 1) / 2;
 			// cout << "ZNALEZIONO " << i + 1 << " = " << t[i] << endl;
 			// cout << "WYJSCIE Z WHILE: " << i + 1 << endl;
 		} else if (lewy_spadek) {
 			is.insert(is.begin(), i);
 			// t[i] = rand() % (r + 1);
 			// t[i] = r;
 			bool skal = (bs[i] - as[i] >= 200);
 			int wsp = (bs[i] - as[i]) / 7;
 			int a = as[i] / (skal ? wsp : 1), b = bs[i] / (skal ? wsp : 1);
 			while (a <= b) {
 				// cout << a << " " << b << endl;
 				int mid = (a + b) / 2;
 				t[i] = mid * (skal ? wsp : 1);
 				czyCieplo(t);
 				t[i] = r;
 				if (czyCieplo(t) == 1) {
 					a = mid + 1;
 				} else {
 					b = mid - 1;
 				}
 			}
 			as[i] = max((b - 1) * (skal ? wsp : 1), 0);
 			t[i] = (b * (skal ? wsp : 1) + r) / 2 + 1;
 			// t[i] = b + rand() % (r - b + 1);
 			// cout << "UPDATE LEWY: " << i + 1 << " " << t[i] << endl;
 			if (b * (skal ? wsp : 1) + 1 == r && !skal) {
 				is.erase(is.begin());
 			}
 		} else if (prawy_spadek) {
 			is.insert(is.begin(), i);
 			// t[i] = 0;
 			bool skal = (bs[i] - as[i] >= 200);
 			int wsp = (bs[i] - as[i]) / 7;
 			int a = as[i] / (skal ? wsp : 1), b = bs[i] / (skal ? wsp : 1);
 			while (a <= b) {
 				int mid = (a + b) / 2;
 				t[i] = mid * (skal ? wsp : 1);
 				czyCieplo(t);
 				t[i] = 0;
 				if (czyCieplo(t) == 1) {
 					b = mid - 1;
 				} else {
 					a = mid + 1;
 				}
 			}
 			bs[i] = min((b + 1) * (skal ? wsp : 1), r);
 			// t[i] = rand() % (b + 1);
 			t[i] = b * (skal ? wsp : 1) / 2;
 			// cout << "UPDATE PRAWY: " << i + 1 << " " << t[i] << endl;
 			if (b == 0 && !skal) {
 				is.erase(is.begin());
 			}
 		} else {
 			is.insert(is.begin(), i);
 			// t[i] = r / 2;
 		}
	}

	znalazlem(t);
	return 0;
}