Блог пользователя ELEPHANT

Автор ELEPHANT, 12 лет назад, По-английски

Hi

Any ideas how to solve this problem?

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

I think you can do such thing:

  1. Compose answer by getting maximum possible prefix of some size and appending 1 or 0 to it

  2. All that you need then is to be able to check whether some prefix can be obtained or not. To do that you can use linear equations modulo 2

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

After you break that one, you can try this one XMAX

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
//v is input array
long long ans = 0;
while (1)
{
    long long t = *max_element(all(v));
    if (t == 0) break;
    fori(sz(v))
        v[i] = min(v[i], v[i] ^ t);
    ans = max(ans, ans ^ t);
}
write ans;