#681093 (C++17) No.873 バイナリ、ヤバいなり！ｗ

• 問題: No.873 バイナリ、ヤバいなり！ｗ
• ユーザー: snrnsidy
• 提出日時: 2021-07-22 21:04:10
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,670 bytes
• コンパイル時間: 1,502 ms
• コンパイル使用メモリ: 134,772 KB
• 実行使用メモリ: 5,824 KB
• 最終ジャッジ日時: 2023-09-24 14:37:29
• 合計ジャッジ時間: 10,243 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	183 ms; 5,676 KB
testcase_02	AC	182 ms; 5,700 KB
testcase_03	AC	182 ms; 5,744 KB
testcase_04	AC	183 ms; 5,632 KB
testcase_05	AC	182 ms; 5,804 KB
testcase_06	AC	182 ms; 5,744 KB
testcase_07	AC	182 ms; 5,676 KB
testcase_08	AC	182 ms; 5,684 KB
testcase_09	AC	182 ms; 5,708 KB
testcase_10	AC	182 ms; 5,744 KB
testcase_11	AC	183 ms; 5,632 KB
testcase_12	AC	182 ms; 5,664 KB
testcase_13	AC	182 ms; 5,820 KB
testcase_14	AC	182 ms; 5,628 KB
testcase_15	AC	182 ms; 5,672 KB
testcase_16	AC	181 ms; 5,668 KB
testcase_17	AC	182 ms; 5,672 KB
testcase_18	AC	182 ms; 5,660 KB
testcase_19	AC	183 ms; 5,676 KB
testcase_20	AC	183 ms; 5,756 KB
testcase_21	AC	182 ms; 5,680 KB
testcase_22	AC	182 ms; 5,668 KB
testcase_23	AC	182 ms; 5,684 KB
testcase_24	AC	182 ms; 5,664 KB
testcase_25	AC	182 ms; 5,632 KB
testcase_26	AC	182 ms; 5,800 KB
testcase_27	AC	182 ms; 5,712 KB
testcase_28	AC	183 ms; 5,684 KB
testcase_29	AC	183 ms; 5,648 KB
testcase_30	AC	182 ms; 5,824 KB
testcase_31	AC	182 ms; 5,716 KB
testcase_32	AC	181 ms; 5,680 KB
testcase_33	AC	183 ms; 5,644 KB
testcase_34	AC	182 ms; 5,668 KB
testcase_35	AC	182 ms; 5,672 KB
testcase_36	AC	182 ms; 5,656 KB
testcase_37	AC	181 ms; 5,692 KB
testcase_38	AC	183 ms; 5,664 KB

ソースコード

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <cstring>
#include <fstream>
#include <random>

using namespace std;

int dp[300001];
int history[300001];
int n;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	fill(dp, dp + 300001, 1e9);
	memset(history, -1, sizeof(history));

	dp[0] = 0;
	for (int i = 0; i <= 300000; i++)
	{
		if (dp[i] >= 1e9) continue;
		for (int j = 1; ; j++)
		{
			if (i + j * j > 300000) break;
			if (dp[i + j * j] >= dp[i] + j)
			{
				dp[i + j * j] = dp[i] + j;
				history[i + j * j] = i;
			}
		}
	}

	cin >> n;

	vector <int> odd, even;

	int num = n;
	while (num > 0)
	{
		int p = history[num];
		int N = sqrt(num - p);
		if (N % 2)
		{
			odd.push_back(N);
		}
		else
		{
			even.push_back(N);
		}
		num = p;
	}

	sort(odd.begin(), odd.end());
	sort(even.rbegin(), even.rend());

	for (int i = 0; i < odd.size(); i++)
	{
		int N = 0;
		for (int j = 0; j < odd[i]; j++)
		{
			cout << N;
			N = 1 - N;
		}
	}
	
	int N = 1;
	int l = 0;
	int r = even.size() - 1;
	bool ok = true;
	while (l<=r)
	{
		N = 1 - N;
		if (ok)
		{
			for (int j = 0; j < even[l]; j++)
			{
				cout << N;
				N = 1 - N;
			}
			l++;
			ok = false;
		}
		else
		{
			for (int j = 0; j < even[r]; j++)
			{
				cout << N;
				N = 1 - N;
			}
			r--;
			ok = true;
		}
	}
	cout << '\n';

	return 0;
}