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
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
enum imie_wykonawcy { ania, mateusz } id;
struct conn {
    int v, p;
};
vector<vector<conn>> read_connections();
auto operator<=>(conn a, conn b) { return a.p <=> b.p; }
conn challange_price(conn c);

int main() {
    {
        string input;
        cin >> input;
        id = (input == "Algosia"s ? ania : mateusz);
    }
    vector<vector<conn>> conns = read_connections();
    int n = conns.size();
    vector<int> prices(n, INT32_MAX);

    priority_queue<conn> que;
    int bas_p = 0;
    que.push({0, 0});

    while (que.size()) {
        conn node;
        do {
            node = que.top();
            que.pop();
        } while (node.p >= prices[node.v] && que.size());
        if (que.size() == 0) break;
        conn newnode = challange_price({node.v, node.p - bas_p});
        newnode.p += bas_p;
        if (newnode.v != node.v) que.push(node);  // if we lost, maybe try again?
        prices[newnode.v] = newnode.p;
        bas_p = newnode.p;
        for (auto i : conns[newnode.v])
            if (i.p + prices[newnode.v] < prices[i.v])  //
                que.push({i.v, i.p + prices[newnode.v]});
    }
    if(id == ania) {
        cout << "!";
        for(auto i : prices)
            cout << " " << i;
        cout << endl;
    }
}

conn challange_price(conn c) {
    // Musimy zmieścić się w 29 bitach.
    // Adres komórki to max 1999, więc mieści się w 11 bitach.
    // Więc zostaje nam 18 bitów.
    // Jedna cena to może być max. 500, co mieści się w 9 bitach.
    // Wymieniamy się cenami, i osoba z niższą ceną wysyła adres.
    for (int i = 0; i < 9; i++) {  // kinda little-endian?
        int bit = (c.p >> i) & 1;
        cout << "+ " << bit << endl;
    }
    int other_price = 0;
    for (int i = 0; i < 9; i++) {
        cout << "?" << endl;
        int bit;
        cin >> bit;
        other_price |= bit << i;
    }
    if (other_price > c.p || (other_price == c.p && id == ania)) {  // We won.
        for (int i = 0; i < 11; i++) {
            int bit = (c.v >> i) & 1;
            cout << "+ " << bit << endl;
        }
    } else {  // We lost;
        int other_vert = 0;
        for (int i = 0; i < 11; i++) {
            cout << "?" << endl;
            int bit;
            cin >> bit;
            other_vert |= bit << i;
        }
        c.v = other_vert;
        c.p = other_price;
    }
    return c;
}

vector<vector<conn>> read_connections() {
    int n, ab;
    cin >> n >> ab;
    vector<vector<conn>> ret(n, vector<conn>(0));
    for (int i = 0; i < ab; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        ret[u].push_back({v, c});
        ret[v].push_back({u, c});
    }
    return ret;
}