p436.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;
};

string input_text;

void read() {
    stringstream buffer;
    buffer << cin.rdbuf();
    input_text = buffer.str();
}

void solve() {
    // Pure implementation. Tokenize the input into decimal numbers, Diputs
    // numbers and "other" characters. A Diputs digit is one of `_.,-~='^"`
    // (least to most significant); a valid Diputs representation lists digits
    // in non-increasing significance and respects per-digit max quantities, so
    // we parse greedily under both constraints. Decimal numbers are parsed
    // greedily up to the Diputs maximum value, with a leading '0' forming the
    // single number 0. The encoding is a mixed-radix system, so conversion in
    // either direction is a small loop instead of enumerating ~836M values.
    // After tokenizing we flip each token's notation, optionally sort the
    // values when the total count is odd, and emit with original separators.

    const string diputs_chars = "_.,-~='^\"";
    const int max_counts[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

    int64_t products[10];
    products[0] = 1;
    for(int i = 0; i < 9; i++) {
        products[i + 1] = products[i] * (max_counts[i] + 1);
    }

    int64_t max_num = products[9] - 1;

    array<int, 256> sig_of;
    sig_of.fill(-1);
    for(int i = 0; i < 9; i++) {
        sig_of[(unsigned char)diputs_chars[i]] = i;
    }

    auto diputs_to_decimal = [&](size_t start, size_t end) -> int64_t {
        int64_t value = 0;
        for(size_t k = start; k < end; k++) {
            value += products[sig_of[(unsigned char)input_text[k]]];
        }
        return value;
    };

    auto decimal_to_diputs = [&](int64_t n) -> string {
        if(n == 0) {
            return "O";
        }
        int counts[9];
        for(int i = 0; i < 9; i++) {
            counts[i] = (n / products[i]) % (max_counts[i] + 1);
        }
        string result;
        for(int i = 8; i >= 0; i--) {
            result.append(counts[i], diputs_chars[i]);
        }
        return result;
    };

    struct token {
        size_t start;
        size_t length;
        int64_t value;
        bool was_decimal;
    };

    vector<token> tokens;

    size_t n = input_text.size();
    for(size_t i = 0; i < n;) {
        unsigned char c = input_text[i];
        if(isdigit(c)) {
            size_t j = i;
            int64_t value = 0;
            if(c == '0') {
                j = i + 1;
            } else {
                while(j < n && isdigit((unsigned char)input_text[j])) {
                    int64_t next_val = value * 10 + (input_text[j] - '0');
                    if(next_val > max_num) {
                        break;
                    }
                    value = next_val;
                    j++;
                }
            }
            tokens.push_back({i, j - i, value, true});
            i = j;
        } else if(c == 'O') {
            tokens.push_back({i, 1, 0, false});
            i++;
        } else if(sig_of[c] >= 0) {
            size_t j = i;
            int last_sig = 8;
            int counts[9] = {};
            while(j < n) {
                int s = sig_of[(unsigned char)input_text[j]];
                if(s < 0 || s > last_sig || counts[s] >= max_counts[s]) {
                    break;
                }
                counts[s]++;
                last_sig = s;
                j++;
            }
            tokens.push_back({i, j - i, diputs_to_decimal(i, j), false});
            i = j;
        } else {
            i++;
        }
    }

    if(tokens.size() % 2 == 1) {
        vector<int64_t> values;
        values.reserve(tokens.size());
        for(auto& t: tokens) {
            values.push_back(t.value);
        }
        sort(values.begin(), values.end());
        for(size_t k = 0; k < tokens.size(); k++) {
            tokens[k].value = values[k];
        }
    }

    string result;
    result.reserve(input_text.size() * 2);
    size_t cursor = 0;
    for(auto& t: tokens) {
        while(cursor < t.start) {
            result += input_text[cursor++];
        }
        if(t.was_decimal) {
            result += decimal_to_diputs(t.value);
        } else {
            result += to_string(t.value);
        }
        cursor = t.start + t.length;
    }

    while(cursor < input_text.size()) {
        result += input_text[cursor++];
    }

    cout << result;
}

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;
}

=================
p436.in1
======================
need 2 sort
O
_

=================
p436.ans2
======================
_
__
O,..__
21
72A72
16
O

=================
p436.in2
======================
1
2
020
___
-A-
,._
0

=================
statement.txt
======================
436. The Diputs notation
time limit per test: 0.5 sec.
memory limit per test: 262144 KB
input: standard
output: standard



The Diputs notation is a notation to represent non-negative integer numbers. Diputs notation has 9 digits, starting with the least significant:

_.,-~='^

There can be a limited quantity of each digit character in the number representation:

Order of digit	Character	ASCII code	Max. quantity
1	_	95	2
2	.	46	3
3	,	44	5
4	-	45	7
5	~	126	11
6	=	61	13
7	'	39	17
8	^	94	19
9	"	34	23

A number representation in Diputs notation starts with the most significant digit, e.g.:

"""^^~~-,..__

Let us write down all possible number representations in Diputs notation and arrange them in the following order. Number A goes after number B if the representation of A in Diputs notation has more `"` (most significant digit) characters than the representation of B. If the numbers A and B have equal number of `"` characters, we then compare the number of '^' characters, and so on. Then we number this sequence, starting from 1 - and the result is the map which defines how numbers are represented in Diputs notation. Zero is represented with the 'O' character (code 79).

Examples:

Decimal notation	Diputs notation
0	O
1	_
2	__
3	.
4	._
6	..
20	,..__
34836480	"
36682648	"^'=~-,._


There is an input containing numbers in decimal notation, numbers in Diputs notation, and some other text. You must output the same numbers, but in another notation: the numbers in decimal notation should be converted to Diputs notation, and the numbers in Diputs notation should be converted to decimals. All numbers in the input are non-negative and do not exceed maximum number representable in Diputs notation. It is possible that the numbers will not be separated by space or other characters. You should parse the numbers in greedy way: when reading a number, you should take maximum number of characters that can form a decimal or Diputs representation of a number. For example, if you have three underscore characters ("___"), you should parse it as numbers "__" (2) and "_" (1) in Diputs notation. In this case, the resulting string will be "21". When parsing decimal numbers, your program should work the same way. There should be no leading zeros in decimal numbers. For example, you should parse the string "020" as decimal numbers 0 and 20, and the result will be "O,..__". If you would get a decimal number larger than the maximum number representable in Diputs notation, you should split it into two or more decimal numbers in greedy way, as described.

Some examples:

Input	Output
___	21
020	O,..__
_12	1,


Because we feel that your task is too easy, you should sort the numbers in ascending order, if the total number of numbers in the input is odd. Only numbers should be reordered; the notation of a number in a certain location should not be changed. For example, for input "2 O _" you should first recognize the notation (decimal, diputs, diputs), then convert it to "__ 0 1", inverting the notation (it is now diputs, decimal, decimal), and then sort the numbers while preserving the notation. Thus, the sorted array is 0, 1 and 2, the notations are (diputs, decimal, decimal), so the answer should be "O 1 2". Take a look at the sample input for better understanding.

Size of input and output will not exceed 1 megabyte (106 bytes).

Sample test(s)

Input
Test #1:

need 2 sort
O
_

Test #2:

1
2
020
___
-A-
,._
0

Output
Test #1:

need O sort
1
2

Test #2:

_
__
O,..__
21
72A72
16
O
Author:	
Resource:	Izhevsk State Technical University Contest 3
Date:	February 06, 2009





=================
p436.ans1
======================
need O sort
1
2

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