Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker,"/STACK:1000000000")
- #include <vector>
- #include <string>
- #include <map>
- #include <cstring>
- #include <queue>
- #include <iostream>
- #include <fstream>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- int nextInt() {
- int x;
- scanf("%d", &x);
- return x;
- }
- char inp[10000];
- string nextString() {
- scanf("%s", inp);
- return inp;
- }
- double nextDouble() {
- double x;
- scanf("%lf", &x);
- return x;
- }
- bool final[1100000];
- int trie[1100000][2];
- int trieSize = 0;
- int newNode() {
- trie[trieSize][0] = -1;
- trie[trieSize][1] = -1;
- ++trieSize;
- return trieSize - 1;
- }
- void deleteNode() {
- --trieSize;
- }
- bool add(int v, int len, string &s, bool added) {
- if (final[v]) {
- return false;
- }
- if (len == 0) {
- final[v] = true;
- return added;
- }
- for (int i = 0; i < 2; ++i) {
- bool wasAdded = false;
- if (trie[v][i] == -1) {
- trie[v][i] = newNode();
- wasAdded = true;
- }
- s += '0' + i;
- if (add(trie[v][i], len - 1, s, added | wasAdded)) {
- return true;
- }
- s.erase(--s.end());
- if (wasAdded) {
- deleteNode();
- }
- }
- return false;
- }
- int main() {
- int n = nextInt();
- vector<int> len(n);
- for (int i = 0; i < n; ++i) {
- len[i] = nextInt();
- }
- vector<int> a(len);
- map<int, vector<string> > res;
- sort(a.begin(), a.end());
- newNode();
- for (int i = 0; i < n; ++i) {
- string s;
- if (!add(0, a[i], s, false)) {
- printf("NO\n");
- return 0;
- }
- res[a[i]].push_back(s);
- }
- printf("YES\n");
- for (int i = 0; i < n; ++i) {
- printf("%s\n", res[len[i]].back().c_str());
- res[len[i]].pop_back();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement