結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2020-08-14 18:18:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 4,420 bytes |
コンパイル時間 | 2,008 ms |
コンパイル使用メモリ | 177,796 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-06-11 14:07:02 |
合計ジャッジ時間 | 3,752 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for (int i = 0; i < (int)(n); i ++)#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)using namespace std;using ll = long long;using PL = pair<ll,ll>;using P = pair<int,int>;constexpr int INF = 1000000000;constexpr long long HINF = 1000000000000000;constexpr long long MOD = 1000000007;// = 998244353;constexpr double EPS = 1e-4;constexpr double PI = 3.14159265358979;template<int Modulus>struct ModInt {long long x;ModInt(long long x = 0) :x((x%Modulus + Modulus)%Modulus) {}constexpr ModInt &operator+=(const ModInt a) {if ((x += a.x) >= Modulus) x -= Modulus; return *this;}constexpr ModInt &operator-=(const ModInt a) {if ((x += Modulus - a.x) >= Modulus) x -= Modulus; return *this;}constexpr ModInt &operator*=(const ModInt a) {(x *= a.x) %= Modulus; return *this;}constexpr ModInt &operator/=(const ModInt a) {return *this *= a.inverse();}constexpr ModInt operator+(const ModInt a) const {return ModInt(*this) += a.x;}constexpr ModInt operator-(const ModInt a) const {return ModInt(*this) -= a.x;}constexpr ModInt operator*(const ModInt a) const {return ModInt(*this) *= a.x;}constexpr ModInt operator/(const ModInt a) const {return ModInt(*this) /= a.x;}friend constexpr ostream& operator<<(ostream& os,const ModInt<Modulus>& a) {return os << a.x;}friend constexpr istream& operator>>(istream& is,ModInt<Modulus>& a) {return is >> a.x;}ModInt inverse() const {// x ^ (-1)long long a = x,b = Modulus,p = 1,q = 0;while (b) {long long d = a/b; a -= d*b; swap(a,b); p -= d*q; swap(p,q);}return ModInt(p);}ModInt pow(long long N) {// x ^ NModInt a = 1;while (N) {if (N&1) a *= *this;*this *= *this;N >>= 1;}return a;}};using mint = ModInt<1000000007>;struct Combination {int N;//using mint = ModInt<1000000007>;//using mint = ModInt<998244353>;vector<mint> fact,ifact,invs;Combination(int N): N(N) {fact.resize(N + 1); ifact.resize(N + 1);fact[0] = fact[1] = 1;ifact[0] = ifact[1] = 1;for (int i = 2;i < N + 1;++i) {fact[i] = fact[i - 1] * i;}ifact[N] = fact[N].inverse();for (int i = N;i >= 1;--i) {ifact[i - 1] = ifact[i] * i;}}void invs_build() {invs.resize(N + 1);invs[1] = 1;for (int i = 2;i < N + 1;++i) invs[i] = fact[i] * ifact[i - 1];}mint operator()(int n, int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[k]*ifact[n - k];}mint npk(int n,int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[n - k];}};int main() {cin.tie(0);ios::sync_with_stdio(false);int N; cin >> N;vector<int> square(1,0);for (int i = 1; i*i <= N; ++i) square.push_back(i*i);vector<int> dp(N + 1,INF);vector<int> before(N + 1);dp[0] = 0; before[0] = -1;rep(i,N) {int j = 0;for (;j*j <= i + 1;j += 2) {if (dp[i + 1] >= dp[i + 1 - j*j] + j) {dp[i + 1] = dp[i + 1 - j*j] + j;before[i + 1] = j;}}while (j*j > i + 1 && j >= 0) --j;if (j%2 == 0) --j;for (;j >= 0; j -= 2) {if (dp[i + 1] >= dp[i + 1 - j*j] + j) {dp[i + 1] = dp[i + 1 - j*j] + j;before[i + 1] = j;}}}vector<int> even,odd;int now = N;while (now > 0) {int x = before[now];if (x%2 == 0) even.push_back(x);else odd.push_back(x);now -= x*x;}sort(even.begin(),even.end());sort(odd.begin(),odd.end());string ans = "";for (int p:odd) {rep(i,p) {if (i%2 == 0) ans += "0";else ans += "1";}}int l = 0,r = (int)even.size() - 1;int cnt = 0;while (l <= r) {if (cnt%2 == 0) {rep(i,even[r]) {if ((i + cnt)%2 == 0) ans += "0";else ans += "1";}--r;} else {rep(i,even[l]) {if ((i + cnt)%2 == 0) ans += "0";else ans += "1";}++l;}++cnt;}cout << ans << '\n';return 0;}