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
#include "cielib.h"

#define ABS(x) ((x)<0 ? -(x) : (x))
#define MIN(x, y) ((x)<(y) ? (x) : (y))
#define GREATER (int)1
#define EQUAL (int)0
#define LESS (int)(-1)
#define INF 1000000005

#define DEBUG true

int D, R, K, POS[505];
int DIR[505];

bool check(){ return czyCieplo(POS); }

int dimPosRelation(int dim, int pos)
{
    if (pos < 0 || pos > R) return 1;
    int originPos = POS[dim];
    POS[dim] = pos; bool rel_1 = check();
    POS[dim] = originPos; bool rel_2 = check();
    if (rel_1) return LESS;
    if (rel_2) return GREATER;
    return EQUAL;
}

bool checkVector(int factor)
{
    int MOVED_POS[505];
    for (int i=0; i<D; ++i) MOVED_POS[i] = POS[i] + DIR[i] * factor;
    return czyCieplo(MOVED_POS);
}

int moveToEdge(int dim){
    int rel_down = dimPosRelation(dim, POS[dim] - 1);
    int rel_up = dimPosRelation(dim, POS[dim] + 1);
    if (rel_down == GREATER && rel_up == GREATER) return EQUAL;
    if (rel_down == GREATER) return GREATER;
    if (rel_up == GREATER) return LESS;
    if (rel_down == EQUAL && rel_up == EQUAL){
        rel_down = dimPosRelation(dim, 0);
        rel_up = dimPosRelation(dim, R);
        if (rel_down == EQUAL && rel_up == EQUAL) return EQUAL;
        int result;
        int boundPos;
        if (rel_down == GREATER){
            boundPos = 0;
            result = GREATER;
        } else {
            boundPos = R;
            result = LESS;
        }

        while (POS[dim] != boundPos-1 && POS[dim] != boundPos+1){
            int midPos = (boundPos + POS[dim]) / 2;
            if (dimPosRelation(dim, midPos) == EQUAL) POS[dim] = midPos;
            else boundPos = midPos;
        }

        return result;
    }
}

int main() {
    D = podajD();
    K = podajK();
    R = podajR();
    for (int i=0; i<D; ++i) POS[i] = R / 2;
    check();

    for (int i=0; i<D; ++i)
    {
        DIR[i] = moveToEdge(i);
    }

    int left = 0, right = INF;
    for (int i=0; i<D; ++i) {
        if (DIR[i] == 1) right = MIN(right, ABS(R - POS[i]));
        else if (DIR[i] == -1) right = MIN(right, POS[i]);
    }
    if (right == INF) right = left;

    while (left != right)
    {
        int mid = (left + right) / 2;
        checkVector(mid);
        if (checkVector(mid + 1)) left = mid+1; else right = mid;
    }

    for (int i=0; i<D; ++i) POS[i] += left * DIR[i];

    if (D != 1 && R%2 == 1)
    {
        for (int i=0; i<D; ++i)
        {
            int rel_down = dimPosRelation(i, POS[i] - 1);
            int rel_up = dimPosRelation(i, POS[i] + 1);
                 if (rel_down == LESS && rel_up == GREATER){ POS[i] -= 1; break; }
            else if (rel_down == EQUAL && rel_up == EQUAL) continue;
            else if (rel_down == EQUAL && rel_up == GREATER){ POS[i] -= 1; continue; }
            else if (rel_down == GREATER && rel_up == LESS){ POS[i] += 1; break; }
            else if (rel_down == GREATER && rel_up == EQUAL){ POS[i] += 1; continue; }
            else if (rel_down == GREATER && rel_up == GREATER) break;
        }
    }

    znalazlem(POS);
}