Submission #1091500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091500		quangminh412	Stove (JOI18_stove)	C++14	0 / 100	1 ms	856 KiB

stove

#include <bits/stdc++.h>
using namespace std;

/*
  John Watson

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int maxn = 130;

int n;
ll k;

ll dp[maxn][2 * maxn][2];

ll magic(int idx, int cur, int isneg)
{
	if (idx == -1)	
		return (cur == 0 && !isneg ? 0 : 1);
	if (dp[idx][120 + cur][isneg] != -1)
		return dp[idx][120 + cur][isneg];
		
	ll res = 0;
		
	for (int i = 0; i < 2; i++)
	{
		int v = (i == 0 ? 1 : -1);
		
		res += magic(idx - 1, cur + v, isneg | (cur + v < 0));
	}
	
	return dp[idx][120 + cur][isneg] = res;
}

string ans = "";
string solve(int idx, int cur)
{
	if (idx == -1) return ans;
	ll s1 = magic(idx - 1, cur + 1, (cur < 0));
	if (s1 >= k)
	{
		ans += '1';
		return solve(idx - 1, cur + 1);
	} 
	k -= s1;
	ans += '0';
	return solve(idx - 1, cur - 1);
}

signed main()
{
	if (fopen("test.inp", "r"))
	{
		freopen("test.inp", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	faster();
	
	cin >> n >> k;
	memset(dp, -1, sizeof(dp));

	solve(n - 1, 0);
	for (char c : ans)
		cout << (c == '1' ? '(' : ')');

	return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:58:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:59:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50