p211.ans1
======================
1 0 1
1 0 2
2 0 1 1 1
1 1 2
1 0 2
3 0 1 1 1 2 1

=================
p211.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<int> queries;

void read() {
    cin >> n >> m;
    queries.resize(m);
    cin >> queries;
}

void solve() {
    // The key is to maintain a register state where adding 2^p never requires
    // long carry chains. Since each register holds {0,1,2} (a redundant base-2
    // representation), the same number has many encodings and we can pick one
    // that keeps carries local. A good approach is to find some invariant that
    // will allow something like this and keep it throughout the updates.
    //
    // A good example for invariant is the following: between any two 2s there
    // is always at least one 0. This guarantees that carries can be absorbed in
    // O(1) changes per addition. The only part is that we should also make sure
    // that the invariant is kept after this addition.
    //
    // For each operation of adding 2^p, let next_two = nearest index > p with
    // reg = 2, and prev_zero = rightmost index < next_two with reg = 0. We
    // consider three cases:
    //
    //     1) p >= prev_zero (no zero between p and next_two):
    //
    //            Change: reg[p]++, reg[next_two] -= 2, reg[next_two+1]++.
    //            Net: +2^p - 2^{next_two+1} + 2^{next_two+1} = +2^p.
    //            3 changes.
    //
    //        The invariant ensures reg[p] < 2 (otherwise p and next_two would
    //        be two 2s with no 0 between them) and reg[next_two+1] < 2
    //        (adjacent to a 2), so both +1s produce <= 2. Invariant is
    //        preserved: if reg[p] becomes 2, reg[next_two] becoming 0 is the
    //        separator above. If reg[next_two+1] becomes 2 it was 1, meaning
    //        next_two was the first 2 above it, so a 0 already existed between
    //        next_two+1 and the next 2 further up. Nothing up there changed.
    //
    //   2) reg[p] != 0 (there is a zero between p and next_two):
    //
    //          Change: reg[p]--, reg[p+1]++.
    //          Net: -2^p + 2^{p+1} = +2^p.
    //          2 changes.
    //
    //      reg[p+1]++ can create a 2 at most, but prev_zero lies between p
    //      and next_two, so a 0 separator already exists nearby.
    //
    //   3) reg[p] == 0:
    //
    //          Change: reg[p]++.
    //          Net: +2^p.
    //          1 change.
    //
    //      No new 2 is created. The 0 at p can't be the sole separator between
    //      two 2s: if reg[p] == 0 then prev_zero >= p, but reaching case 3
    //      requires skipping case 1, which means either next_two > n (no 2
    //      above) or prev_zero > p (another 0 above p still separates).

    vector<int> reg(n + 2, 0);
    set<int> pos_for_val[3];
    for(int i = 0; i <= n; i++) {
        pos_for_val[0].insert(i);
    }
    pos_for_val[2].insert(n + 1);

    auto apply = [&](int pos, int delta) {
        pos_for_val[reg[pos]].erase(pos);
        reg[pos] += delta;
        pos_for_val[reg[pos]].insert(pos);
        cout << ' ' << pos << ' ' << reg[pos];
    };

    for(int p: queries) {
        int next_two = *pos_for_val[2].upper_bound(p);
        int prev_zero = *prev(pos_for_val[0].lower_bound(next_two));

        if(next_two <= n && p >= prev_zero) {
            cout << 3;
            apply(p, 1);
            apply(next_two, -2);
            apply(next_two + 1, 1);
        } else if(reg[p] != 0) {
            cout << 2;
            apply(p, -1);
            apply(p + 1, 1);
        } else {
            cout << 1;
            apply(p, 1);
        }
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p211.in1
======================
5
6
0 0 0 1 0 0

=================
statement.txt
======================
211. Strange Counter
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The new secret counter invented in one theoretical computer science lab is the great breakthrough in the computer microschemes design. This counter consists of N registers numbered from 0 to N-1, each of which contains 0, 1 or 2. If the number in the i-th register is Ai, the number stored in the counter is


AN-1 * 2N-1 + AN-2 * 2N-2 + ... + A1 * 2 + A0


One can see that the same number can be stored in the counter in several different ways. For example, the number 5 can be stored in a 3-register counter as (1, 0, 1) or as (0, 2, 1).

The main feature of the counter is that it can add numbers that are powers of two to the number stored in the counter, only changing the value of a small number of registers. Namely, the scientists of the lab developed the scheme that allowed adding such number changing no more than four registers!

Unfortunately after the recent experiments in the neighbouring physics lab, involving the creation of the artificial black hole, the theoretical computer science laboratory was accidently destroyed. However, the supercomputer project that the counter was designed for is still on, so you were asked to reinvent the counter.

Input

The first line of the input file contains N — the number of registers in the counter (1 ≤ N ≤ 1 000). Initially all registers contain zeroes. The second line contains M — the number of additions you have to make (1 ≤ M ≤ 10 000). The third line contains M integer numbers ranging from 0 to N-1. Number i means that you must add 2i to the number in the counter. There sum of all numbers added to the counter does not exceed 2N - 1.

Output

Output file must contain M lines. Each line must contain the changes made adding the corresponding number to the counter.

The first number in each line must be K — the number of registers changed (1 ≤ K ≤ 4). K pairs must follow — for each changed register first output its number and then the new value.

Sample test(s)

Input
5
6
0 0 0 1 0 0

Output
1 0 1
1 0 2
2 0 1 1 1
1 1 2
1 0 2
3 0 1 1 1 2 1
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-30

=================
