#include <bits/stdc++.h> using namespace std; using LL = long long; #define e1 first #define e2 second #define pb push_back #define OUT(x) {cout << x << "\n"; exit(0); } #define TCOUT(x) {cout << x << "\n"; return; } #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define rep(i, l, r) for(int i = (l); i < (r); ++i) #define boost {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } #define sz(x) int(x.size()) #define trav(a, x) for(auto& a : x) #define all(x) begin(x), end(x) typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; /*#include <atcoder/modint> using namespace atcoder; using mint = modint998244353; vector <mint> fac, inv; mint binom(int n, int k) { if (n < k || n < 0) return 0; return fac[n] * inv[k] * inv[n-k]; } void prep(int N) { fac.resize(N+1, 1); inv.resize(N+1, 1); for (int i=1; i<=N; ++i) fac[i] = fac[i-1] * i; inv[N] = fac[N].inv(); for (int i=N-1; i>0; --i) inv[i] = inv[i+1] * (i + 1); }*/ mt19937_64 rng(time(0)); int random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } #ifdef DEBUG template<class T> int size(T &&x) { return int(x.size()); } template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) { return out << '(' << p.first << ", " << p.second << ')'; } template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) { out << '{'; for(auto it = x.begin(); it != x.end(); ++it) out << *it << (it == prev(x.end()) ? "" : ", "); return out << '}'; } void dump() {} template<class T, class... Args> void dump(T &&x, Args... args) { cerr << x << "; "; dump(args...); } #endif #ifdef DEBUG struct Nl{~Nl(){cerr << '\n';}}; # define debug(x...) cerr << (strcmp(#x, "") ? #x ": " : ""), dump(x), Nl(), cerr << "" #else # define debug(...) 0 && cerr #endif const int maxn = 1000100; //Did you REAALLY consider sample tests? void solve() { int n; cin >> n; string s; cin >> s; int zer = 0, jed = 0; vector <int> znaki(15, 0); rep(i, 0, 8*n) { if (s[i] == '0') ++zer; else ++jed; } int pocz = 'a', kon = 'z'; FOR(i, pocz, kon) znaki[__builtin_popcount(i)] = i; int front = 0; while (znaki[front] == 0) ++front; int back = 14; while (znaki[back] == 0) --back; auto ok = [&](int nn, int jedynek) -> bool { return front * nn <= jedynek && jedynek <= back * nn; }; if (!(ok(n, jed))) TCOUT("NIE"); string wyn = ""; int remains = n; FOR(step, 1, n) { bool flag = false; FOR(zabiore, front, back) { if (!flag && ok(remains - 1, jed - zabiore)) { flag = 1; remains--; jed -= zabiore; wyn += (char)(znaki[zabiore]); } } assert(flag); } assert(sz(wyn) == n); cout << wyn << "\n"; } int main() { boost; int tests; //cin >> tests; tests = 1; FOR(test, 1, tests) { solve(); } }
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 114 115 116 117 118 119 | #include <bits/stdc++.h> using namespace std; using LL = long long; #define e1 first #define e2 second #define pb push_back #define OUT(x) {cout << x << "\n"; exit(0); } #define TCOUT(x) {cout << x << "\n"; return; } #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define rep(i, l, r) for(int i = (l); i < (r); ++i) #define boost {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } #define sz(x) int(x.size()) #define trav(a, x) for(auto& a : x) #define all(x) begin(x), end(x) typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; /*#include <atcoder/modint> using namespace atcoder; using mint = modint998244353; vector <mint> fac, inv; mint binom(int n, int k) { if (n < k || n < 0) return 0; return fac[n] * inv[k] * inv[n-k]; } void prep(int N) { fac.resize(N+1, 1); inv.resize(N+1, 1); for (int i=1; i<=N; ++i) fac[i] = fac[i-1] * i; inv[N] = fac[N].inv(); for (int i=N-1; i>0; --i) inv[i] = inv[i+1] * (i + 1); }*/ mt19937_64 rng(time(0)); int random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } #ifdef DEBUG template<class T> int size(T &&x) { return int(x.size()); } template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) { return out << '(' << p.first << ", " << p.second << ')'; } template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) { out << '{'; for(auto it = x.begin(); it != x.end(); ++it) out << *it << (it == prev(x.end()) ? "" : ", "); return out << '}'; } void dump() {} template<class T, class... Args> void dump(T &&x, Args... args) { cerr << x << "; "; dump(args...); } #endif #ifdef DEBUG struct Nl{~Nl(){cerr << '\n';}}; # define debug(x...) cerr << (strcmp(#x, "") ? #x ": " : ""), dump(x), Nl(), cerr << "" #else # define debug(...) 0 && cerr #endif const int maxn = 1000100; //Did you REAALLY consider sample tests? void solve() { int n; cin >> n; string s; cin >> s; int zer = 0, jed = 0; vector <int> znaki(15, 0); rep(i, 0, 8*n) { if (s[i] == '0') ++zer; else ++jed; } int pocz = 'a', kon = 'z'; FOR(i, pocz, kon) znaki[__builtin_popcount(i)] = i; int front = 0; while (znaki[front] == 0) ++front; int back = 14; while (znaki[back] == 0) --back; auto ok = [&](int nn, int jedynek) -> bool { return front * nn <= jedynek && jedynek <= back * nn; }; if (!(ok(n, jed))) TCOUT("NIE"); string wyn = ""; int remains = n; FOR(step, 1, n) { bool flag = false; FOR(zabiore, front, back) { if (!flag && ok(remains - 1, jed - zabiore)) { flag = 1; remains--; jed -= zabiore; wyn += (char)(znaki[zabiore]); } } assert(flag); } assert(sz(wyn) == n); cout << wyn << "\n"; } int main() { boost; int tests; //cin >> tests; tests = 1; FOR(test, 1, tests) { solve(); } } |