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

const int N = 505;

int d, n, t[N], edge[N], cnt, border[N], sz;
vector<int> now;

void checkOnEdge(int pos) {
    if (edge[pos]) return;

    bool ok = false;

    --t[pos];
    czyCieplo(t);
    ++t[pos];
    if (czyCieplo(t)) ok = true;

    if (ok) {
        edge[pos] = 1;
        ++cnt;
        now.push_back(pos);
    }
}

void go(int *a, int n) {
    if (n == 1) {
        checkOnEdge(a[0]);
        return;
    }
    bool ok = false;
    for (int i = 0; i < n; ++i) t[a[i]] -= 1;
    czyCieplo(t);
    for (int i = 0; i < n; ++i) t[a[i]] += 1;
    if (czyCieplo(t)) ok = true;

    if (!ok) return;
    int n1 = n / 2;
    int n2 = n - n1;
    go(a, n1);
    go(a + n1, n2);
}

void solve() {
    while (cnt < d) {
        sz = 0;
        int prv = cnt;
        for (int i = 0; i < d; ++i) {
            if (!edge[i]) border[sz++] = i;
        }
        go(border, sz);
        if (prv == cnt) {
            break;
        }
        int l = 0, r = n - 1;
        for (auto& i : now) r = min(r, n - t[i] - 1);
        while (r - l > 1) {
            int m = (l + r) / 2;
            bool ok = true;
            for (auto& i : now) t[i] += m;
            czyCieplo(t);
            for (auto& i : now) ++t[i];
            ok = czyCieplo(t);
            for (auto& i : now) t[i] -= m + 1;
            if (ok) l = m; else r = m;
        }
        for (auto& i : now) t[i] += r;
    }
}

void correct(int pos) {
    int cur = 0;
    --t[pos];
    czyCieplo(t);
    ++t[pos];
    if (czyCieplo(t)) cur |= 1;
    ++t[pos];
    czyCieplo(t);
    --t[pos];
    if (czyCieplo(t)) cur |= 2;
    if (cur == 1) {
        ++t[pos];
    }
    if (cur == 2) {
        --t[pos];
    }
}

int main() {
	d = podajD();
    n = podajR();
	for(int i = 0; i < d; ++i) {
		t[i] = 1;
    }
    solve();
    for (int i = 0; i < d; ++i) {
        correct(i);
    }
	znalazlem(t);
    return 0;
}