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
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cassert>
#include <chrono>
#include <bitset>
using namespace std;

namespace des
{

  struct Rozkaz
  {
    int poczatek;
    int koniec;
  };

  bool czyBitZapalony(unsigned long long uporzadkowanie, unsigned long long numerBitu)
  {
    return (uporzadkowanie & (1ll << numerBitu));
  }

  unsigned long long zapalBit(unsigned long long uporzadkowanie, unsigned long long numerBitu)
  {
    uporzadkowanie = uporzadkowanie | (1ll << numerBitu);
    return uporzadkowanie;
  }

  unsigned long long zgasBit(unsigned long long uporzadkowanie, unsigned long long numerBitu)
  {
    uporzadkowanie = uporzadkowanie & (~(1ll << numerBitu));
    return uporzadkowanie;
  }

  unsigned long long applyRozkaz(unsigned long long uporzadkowanie, Rozkaz const& rozkaz)
  {
    unsigned long long result = uporzadkowanie;
    if (czyBitZapalony(uporzadkowanie, rozkaz.poczatek) && !czyBitZapalony(uporzadkowanie, rozkaz.koniec))
    {
      result = zgasBit(result, rozkaz.poczatek);
      result = zapalBit(result, rozkaz.koniec);
    }
    return result;
  }


  unsigned long long policzLiczbeWczesniejszychKonfiguracji(unsigned long long uporzadkowanie, std::vector<des::Rozkaz> & rozkazy, int ktoryRozkaz)
  {
    if (ktoryRozkaz < 0)
      return 1;
    des::Rozkaz rozkaz = rozkazy[ktoryRozkaz];
    bool pierwszyZapalony = czyBitZapalony(uporzadkowanie, rozkaz.poczatek);
    bool drugiZapalony = czyBitZapalony(uporzadkowanie, rozkaz.koniec);
    if (pierwszyZapalony == drugiZapalony)
      return policzLiczbeWczesniejszychKonfiguracji(uporzadkowanie, rozkazy, ktoryRozkaz-1);
    if (pierwszyZapalony && ! drugiZapalony)
      return 0;
    unsigned long long suma = 0;
    suma += policzLiczbeWczesniejszychKonfiguracji(uporzadkowanie, rozkazy, ktoryRozkaz - 1);
    unsigned long long noweUporzadkowanie = uporzadkowanie;
    noweUporzadkowanie = zapalBit(noweUporzadkowanie, rozkaz.poczatek);
    noweUporzadkowanie = zgasBit(noweUporzadkowanie, rozkaz.koniec);
    suma += policzLiczbeWczesniejszychKonfiguracji(noweUporzadkowanie, rozkazy, ktoryRozkaz - 1);
    return suma;
  }

}

int main()
{
  int iloscZolnierzy;
  int iloscRozkazow;
  std::cin >> iloscZolnierzy >> iloscRozkazow;

  std::vector<des::Rozkaz> rozkazy;
  for (int i = 0; i < iloscRozkazow; ++i)
  {
    des::Rozkaz rozkaz;
    std::cin >> rozkaz.poczatek >> rozkaz.koniec;
    rozkaz.poczatek--;
    rozkaz.koniec--;
    rozkazy.push_back(rozkaz);
  }

  std::vector<unsigned long long> sumaDobrych(iloscZolnierzy + 1, 0);
  for (int pierwszyGotowy = 0; pierwszyGotowy < iloscZolnierzy; ++pierwszyGotowy)
  {
    for (int ostatniGotowy = pierwszyGotowy; ostatniGotowy < iloscZolnierzy; ++ostatniGotowy)
    {
      unsigned long long koncoweUporzadkowanie = 0;
      for (int i = pierwszyGotowy; i <= ostatniGotowy; ++i)
      {
        koncoweUporzadkowanie= des::zapalBit(koncoweUporzadkowanie, i);
      }
      int ilosc = ostatniGotowy - pierwszyGotowy + 1;
      sumaDobrych[ilosc] += policzLiczbeWczesniejszychKonfiguracji(koncoweUporzadkowanie, rozkazy, rozkazy.size()-1);
    }
  }

  /*for (int i = 1; i <= iloscZolnierzy; ++i)
  {
    std::cout << sumaDobrych[i] << " ";
  }*/
  //std::cout << "\n";
  for (int i = 1; i <= iloscZolnierzy; ++i)
  {
    std::cout << (sumaDobrych[i] % 2) << " ";
  }
  std::cout << "\n";

  return 0;
}