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
/* 2016
 * Maciej Szeptuch
 */
#include <algorithm>

#include "cielib.h"

int dimensions;
int range;
int position[512];
int diagonal[512];

bool am_i_closer(int pos[512]);
void find_boundary(int d, int version);

int main(void)
{
    range = podajR();
    dimensions = podajD();

    for(int d = 0; d < dimensions; ++ d)
        position[d] = range / 2;

    am_i_closer(position);
    for(int d = 0; d < dimensions; ++ d)
    {
        diagonal[d] = -1;
        find_boundary(d, 0);
    }

    for(int d = 0; d < dimensions; ++ d)
    {
        if(position[d] < range)
            continue;

        diagonal[d] = 1;
        find_boundary(d, 1);
    }

    {
        int from = 0;
        int to = range;
        for(int d = 0; d < dimensions; ++ d)
            to = std::min(to, diagonal[d] > 0 ? range - position[d] : position[d]);

        while(from < to)
        {
            int mid = (from + to + 1) / 2;
            for(int d = 0; d < dimensions; ++ d)
                position[d] += mid * diagonal[d];

            if(am_i_closer(position))
                from = mid;

            else
                to = mid - 1;

            for(int d = 0; d < dimensions; ++ d)
                position[d] -= mid * diagonal[d];
        }

        for(int d = 0; d < dimensions; ++ d)
            position[d] += from * diagonal[d];
    }

    znalazlem(position);
    return 0;
}

bool am_i_closer(int pos[512])
{
    for(int d = 0; d < dimensions; ++ d)
        if(pos[d] < 0 || pos[d] > range)
            return false;

    return czyCieplo(pos);
}

void find_boundary(int d, int version)
{
    int from = version ? 0 : position[d];
    int to = version ? position[d] : range;
    while(from < to)
    {
        int mid = (from + to + (version ? 0 : 1)) / 2;
        position[d] = mid;
        bool closer = am_i_closer(position);
        if(closer)
        {
            if(version)
                to = mid;

            else
                from = mid;

            continue;
        }

        position[d] = version ? to : from;
        closer = am_i_closer(position);
        if(closer)
        {
            if(version)
                from = mid + 1;

            else
                to = mid - 1;

            continue;
        }

        if(version)
            to = mid;

        else
            from = mid;
    }

    position[d] = from;
}