結果
| 問題 |
No.2671 NUPC Decompressor
|
| コンテスト | |
| ユーザー |
 GEX777
|
| 提出日時 | 2024-03-15 21:35:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 28 ms / 2,000 ms |
| コード長 | 15,813 bytes |
| コンパイル時間 | 1,925 ms |
| コンパイル使用メモリ | 156,656 KB |
| 最終ジャッジ日時 | 2025-02-20 04:41:42 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
/**
* @file template.cpp
* @brief 競技プログラミングのデッキ
* @author Gex777
* @date update:2024/03/10
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>
#include <functional>
// #include <atcoder/all> //ACL
using namespace std;
// using namespace atcoder;
// 独自型定義
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
// マクロの宣言
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), e.rend()
// 定数宣言
constexpr double PI = 3.141592653589793;
constexpr ll MOD998 = 998244353;
constexpr ll MOD107 = 1000000007;
/****************************************************
*************ここから下は自作ライブラリ**************
****************************************************/
// コンテナの中身を表示, 1行で出力をする, debug用
template <typename T>
void printv(T &a)
{
for (const auto &x : a)
{
cout << x << " ";
}
puts("");
return;
}
// コンテナの中身を表示, 二次元配列用
template <typename T>
void printvv(T &a)
{
for (const auto &x : a)
{
printv(x);
}
}
// コンテナの中身を表示, pair型
template <typename T>
void print_vpair(const T &a)
{
for (const auto &x : a)
{
cout << "(" << x.first << ", " << x.second << "), ";
}
puts("");
return;
}
template <class T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
// コンテナの中身を表示, 改行して出力をする, debug用
template <typename T>
void println(T &a)
{
for (const auto &x : a)
{
cout << x << endl;
}
return;
}
// 1~Nまでの総和を求める
ll sum_from_1_to_N(ll N)
{
if (N < 1LL)
{
return 0;
}
if ((N & 1) == 0) // even
{
return N / 2 * (N + 1);
}
else // odd
{
return (N + 1) / 2 * N;
}
}
// A+1~Nまでの総和を求める
ll sum_from_A_to_B(ll A, ll B)
{
return sum_from_1_to_N(B) - sum_from_1_to_N(A);
}
// a^bを求める, 繰り返し2乗法を用いる,3番目の引数はModを取る場合に設定
ll intPowMod(ll a, ll b, const ll MOD = LLONG_MAX)
{
ll ans = 1;
ll A = a;
while (b > 0)
{
int n = b % 2;
b /= 2;
if (n == 1)
{
ans *= A % MOD;
ans %= MOD;
}
A = ((A % MOD) * (A % MOD)) % MOD;
}
return ans;
}
ld arg_to_rad(ld arg) { return (arg * PI / 180.0); }
ld rad_to_arg(ld rad) { return rad * 180.0 / PI; }
// C(n, m)を求める
ll combination(const ll n, const ll m)
{
assert(n >= m); // n>=mは保証される
ll up = 1;
ll down = 1;
for (int i = n; i > n - m; i--)
{
up *= i;
}
for (int i = m; i >= 2; i--)
{
down *= i;
}
return up / down;
}
// 動的計画法で前処理,O(N**2)
vvll combination_table(const int MAX_N = 50)
{
vvll com = vvll(MAX_N + 1, vll(MAX_N + 1, 0)); // 前計算の結果を保存
com[0][0] = 1;
for (int i = 1; i <= MAX_N; ++i)
{
com[i][0] = 1;
for (int j = 1; j <= MAX_N; j++)
{
com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);
}
}
return com;
}
// a÷bをMODで割ったあまりを返す関数
ll DivisionMod(ll a, ll b, ll MOD)
{
return (a * intPowMod(b, MOD - 2, MOD)) % MOD;
}
// C(n, r)をModで割った余りを返す関数, 3番めの引数を入れないと通常のConbination
ll combinationMod(ll n, ll r, ll MOD = LLONG_MAX)
{
// 分子upを求める
ll up = 1;
for (ll i = n - r + 1; i <= n; ++i)
{
up = (up * i) % MOD;
}
// 分母downを求める
ll down = 1;
for (ll i = 1; i <= r; ++i)
down = (down * i) % MOD;
return DivisionMod(up, down, MOD);
}
// a,bの最大公約数を求める, A>=B>=0の時, 計算量O(logB)
long long GCD(long long a, long long b)
{
if (b == 0)
return a;
else
return GCD(b, a % b);
}
// 拡張ユークリッドの互助法, 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
long long d = extGCD(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 最小公倍数
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
// 素数判定, P->true, not_P->false
bool check_Prime(ll N)
{
if (N == 2)
return true;
if (N == 1 || (N & 1) == 0)
return false;
for (ll i = 3; i <= sqrt(N); i += 2)
{
if (N % i == 0)
return false;
}
return true;
}
// 素因数分解,key:素数, value:指数のmap<ll,ll>を返す
map<ll, ll> prime_factorize(ll number)
{
if (number == 1)
{
return {{1LL, 1LL}};
}
map<ll, ll> table;
for (ll i = 2; i * i <= number; ++i)
{
while (number % i == 0)
{
table[i]++;
number /= i;
}
}
if (number != 1LL)
{
table[number]++;
}
return table;
}
// Eratosthenesのtableを使った素因数分解
vector<pii> prime_factorize(ll number, const vi &IsPrime)
{
if (number == 1)
{
return {{1, 1}};
}
vector<pii> factor;
while (number != 1)
{
int cnt = 0;
int f = IsPrime[number];
while (IsPrime[number] == f)
{
number /= IsPrime[number];
++cnt;
}
factor.push_back({f, cnt});
}
return factor;
}
/* エラストステネス and 高速素因数分解
prime->IsPrime[i]=i; not prime ->最小の素因数
高速素因数分解をするのにはprime_factorize(ll num, ll table)を使う */
vi Eratosthenes(size_t max_number)
{
vi IsPrime(max_number + 1);
// tableの初期化
for (int i = 1; i < IsPrime.size(); ++i)
{
IsPrime[i] = i;
}
for (int i = 2; i <= sqrt(max_number); ++i)
{
for (int j = i; j <= max_number; j += i)
{
if (IsPrime[j] == j)
{
IsPrime[j] = i;
}
}
}
return IsPrime;
}
// O(N)でNの階乗を求める
ll factorial(const ll N)
{
ll ans = 1;
for (ll i = 1; i <= N; ++i)
{
ans *= i;
}
return ans;
}
// Run Length Encoding, ランレングス圧縮
template <typename T>
vector<pair<T, int>> RLE(const vector<T> &A)
{
vector<pair<T, int>> rle;
rle.push_back({A.front(), 1});
for (int i = 1; i < A.size(); ++i)
{
if (rle.back().first == A[i])
{
rle.back().second++;
}
else
{
rle.push_back({A[i], 1});
}
}
return rle;
}
vector<pair<char, int>> RLE(const string &S)
{
vector<pair<char, int>> rle;
rle.push_back({S.front(), 1});
for (int i = 1; i < S.size(); ++i)
{
if (rle.back().first == S[i])
{
rle.back().second++;
}
else
{
rle.push_back({S[i], 1});
}
}
return rle;
}
void DEBUG_INDICATE()
{
static int cnt = 0;
cout << "-----DEBUG:" << cnt++ << "------" << endl;
return;
}
// 正方行列の回転を行うライブラリ
template <typename T>
struct ROTATE
{
static vector<vector<T>> clockwise(const vector<vector<T>> &X)
{
assert(X.size() == X[0].size());
const int N = X.size();
vector<vector<T>> Y(N, vector<T>(N));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
Y[j][N - 1 - i] = X[i][j];
return Y;
}
static vector<vector<T>> anticlockwise(const vector<vector<T>> &X)
{
assert(X.size() == X[0].size());
const int N = X.size();
vector<vector<T>> Y(N, vector<T>(N));
for (int i = 0; i < N; ++i)
for (int j = N - 1; 0 <= j; --j)
Y[N - 1 - j][i] = X[i][j];
return Y;
}
};
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RangeMinimumQuery
{
const T INF = numeric_limits<T>::max();
int n; // 葉の数
vector<T> dat; // 完全二分木の配列
RangeMinimumQuery(int n_) : n(), dat(n_ * 4, INF)
{ // 葉の数は 2^x の形
int x = 1;
while (n_ > x)
{
x *= 2;
}
n = x;
}
void update(int i, T x)
{
i += n - 1;
dat[i] = x;
while (i > 0)
{
i = (i - 1) / 2; // parent
dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
{
return INF;
}
else if (a <= l && r <= b)
{
return dat[k];
}
else
{
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
};
// 1次元累積和のためのクラス
template <typename T>
struct CSUM1D
{
vector<T> csum;
// 1次元累積和にするコンストラクタ
CSUM1D(const vector<T> &_csum)
{
const size_t N = _csum.size();
csum = vll(N + 1, 0);
for (int i = 0; i < N; ++i)
csum[i + 1] = csum[i] + _csum[i];
}
// 区間[L,R]の合計値(閉区間)
T get(const int L, const int R)
{
const size_t N = csum.size();
assert(1 <= L && L <= R && R <= N);
return csum[R] - csum[L-1];
}
};
// 二次元累積和のためのクラス
template <typename T>
struct CSUM2D
{
vector<vector<T>> csum;
// 二次元累積和にするコンストラクタ
CSUM2D(const vector<vector<T>> &_csum)
{
const int N = _csum.size();
const int M = _csum[0].size();
csum = vector<vector<T>>(N + 1, vector<T>(M + 1, 0));
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
csum[i][j] = _csum[i - 1][j - 1];
for (int i = 0; i <= N; ++i)
for (int j = 0; j < M; ++j)
csum[i][j + 1] = csum[i][j] + csum[i][j + 1];
for (int j = 0; j <= M; ++j)
for (int i = 0; i < N; ++i)
csum[i + 1][j] = csum[i][j] + csum[i + 1][j];
}
//(i1,j1)を左上,(i2,j2)を右下とする長方形領域の合計値(閉区間)
T get(const int i1, const int j1, const int i2, const int j2)
{
assert(i1 <= i2 && j1 <= j2);
assert(1 <= i1 && i1 < csum.size() && 1 <= j1 && j1 < csum[0].size());
assert(1 <= i2 && i2 < csum.size() && 1 <= j2 && j2 < csum[0].size());
T s4 = csum[i2][j2];
T s1 = csum[i1 - 1][j1 - 1];
T s2 = csum[i1 - 1][j2];
T s3 = csum[i2][j1 - 1];
return s4 - s3 - s2 + s1;
}
};
/**
* @brief 要素数N,二項演算op, 初期値INFを指定するセグ木
* update(i,x): i 番目の要素を x に更新。O(log(n))
* query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct SegTree
{
T INF; // 初期値
int N; // 葉の数
vector<T> data; // 完全二分木の配列
function<T(T, T)> op; // 二項演算
SegTree(int _N, const function<T(T, T)> _op, const T _INF) : N(), data(_N * 4, _INF), op(_op), INF(_INF)
{ // 葉の数は 2^x の形
int x = 1;
while (_N > x)
{
x *= 2;
}
N = x;
}
void update(int i, T x)
{
i += N - 1;
data[i] = x;
while (i > 0)
{
i = (i - 1) / 2; // parent
data[i] = op(data[i * 2 + 1], data[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, N); }
T query_sub(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
{
return INF;
}
else if (a <= l && r <= b)
{
return data[k];
}
else
{
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return op(vl, vr);
}
}
// 添字でアクセス
T operator[](int i)
{
return data[i + N - 1];
}
};
// Union-Find
struct UnionFind
{
vector<int> par, rank, siz;
// 構造体の初期化
UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}
// 根を求める
int root(int x)
{
if (par[x] == -1)
return x; // x が根の場合は x を返す
else
return par[x] = root(par[x]); // 経路圧縮
}
// x と y が同じグループに属するか (= 根が一致するか)
bool issame(int x, int y) { return root(x) == root(y); }
// x を含むグループと y を含むグループを併合する
bool unite(int x, int y)
{
int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
if (rx == ry)
return false; // すでに同じグループのときは何もしない
// union by rank
if (rank[rx] < rank[ry])
swap(rx, ry); // ry 側の rank が小さくなるようにする
par[ry] = rx; // ry を rx の子とする
if (rank[rx] == rank[ry])
rank[rx]++; // rx 側の rank を調整する
siz[rx] += siz[ry]; // rx 側の siz を調整する
return true;
}
// x を含む根付き木のサイズを求める
int size(int x) { return siz[root(x)]; }
};
/*********************************************
*************ライブラリ終わり******************
***********************************************/
int main()
{
int K;
cin >> K;
vs NUPC;
for(int i=0; i<(1<<4); ++i)
{
string temp;
for(int bit=3; 0<=bit; --bit)
{
temp += (i & (1<<bit))?'1':'0';
}
string nupc = "N#U#P#C#";
for(int j=0; j<4; ++j)
{
nupc[j*2+1] = temp[j]+1;
}
// cout << "temp=" << temp << endl;
NUPC.push_back(nupc);
}
// DEBUG_INDICATE();
// println(NUPC);
// DEBUG_INDICATE();
for(string &S: NUPC)
{
string T;
for(int i=0; i<S.size(); ++i)
{
if(i%2 == 0)
{
T+=S[i];
}
else if(S[i]=='1')
{
T += T;
}
}
S = T;
}
sort(all(NUPC));
cout << NUPC[K-1] << endl;
}