fork download 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2024-11-30 23:03:19
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2024-12-01 00:23:03
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  16. #define int long long
  17. #define ll long long 
  18. #define ull unsigned long long
  19. #define sz(x) x.size()
  20. #define sqr(x) (1LL * (x) * (x))
  21. #define all(x) x.begin(), x.end()
  22. #define fill(f,x) memset(f,x,sizeof(f))
  23. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  24. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  25. #define debug(x) cout << #x << " = " << x << '\n'
  26. #define ii pair<int,int>
  27. #define iii pair<int,ii>
  28. #define di pair<ii,ii>
  29. #define vi vector<int>
  30. #define vii vector<ii>
  31. #define mii map<int,int>
  32. #define fi first
  33. #define se second
  34. #define pb push_back
  35. #define MOD 1000000007
  36. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  37. #define YES cout << "YES\n"
  38. #define NO cout << "NO\n"
  39. #define MASK(i) (1LL << (i))
  40. #define c_bit(i) __builtin_popcountll(i)
  41. #define BIT(x,i) ((x) & MASK(i))
  42. #define SET_ON(x,i) ((x) | MASK(i))
  43. #define SET_OFF(x,i) ((x) & ~MASK(i))
  44. #define oo 1e18
  45. #define name "QPALIN"
  46. #define endl '\n'
  47. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms."
  48. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  49. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  50. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  51. int n,k;
  52. string omega,t;
  53.  
  54. struct bignum {
  55.  
  56.     string s;
  57.  
  58.     bignum() {
  59.         this->s = "0";
  60.     }
  61.  
  62.     bignum(string a) {
  63.         s = a;
  64.     }
  65.  
  66.     bignum(int a) {
  67.         s = to_string(a);
  68.     }
  69.  
  70.     friend istream &operator>>(istream &is, bignum &a) {
  71.         is >> a.s;
  72.         return is;
  73.     }
  74.  
  75.     friend ostream &operator<<(ostream &os, const bignum &a) {
  76.         os << a.s;
  77.         return os;
  78.     }
  79.  
  80.     bool operator<(const bignum &a) const {
  81.         if (sz(s) < sz(a.s)) return 1;
  82.         if (sz(s) > sz(a.s)) return 0;
  83.         return s < a.s;
  84.     }
  85.  
  86.     bool operator>(const bignum &a) const {
  87.         if (sz(s) > sz(a.s)) return 1;
  88.         if (sz(s) < sz(a.s)) return 0;
  89.         return s > a.s;
  90.     }
  91.  
  92.     bool operator==(const bignum &a) {
  93.         return s == a.s;
  94.     }
  95.  
  96.     bool operator!=(const bignum &a) {
  97.         return s != a.s;
  98.     }
  99.  
  100.     bool operator<=(const bignum &a) {
  101.         if (sz(s) < sz(a.s)) return 1;
  102.         if (sz(s) > sz(a.s)) return 0;
  103.         return s <= a.s;
  104.     }
  105.  
  106.     bool operator>=(const bignum &a) {
  107.         if (sz(s) > sz(a.s)) return 1;
  108.         if (sz(s) < sz(a.s)) return 0;
  109.         return s >= a.s;
  110.     }
  111.  
  112.     bignum operator+(const bignum &a) {
  113.         string x = "";
  114.         int m = s.size(), n = a.s.size();
  115.         int d = abs(m-n), c = 0;
  116.         FOD(i,min(n,m)-1,0) 
  117.         {
  118.             int sum = c;
  119.             if (m < n) sum += s[i]-'0'+a.s[i+d]-'0';
  120.             else sum += s[i+d]-'0'+a.s[i]-'0';
  121.             x += sum%10+'0';
  122.             c = sum/10;
  123.         }
  124.         if (m < n) 
  125.             FOD(i,n-m-1,0) 
  126.         	{
  127.                 int sum = ((a.s[i]-'0')+c);
  128.                 x += sum%10+'0';
  129.                 c = sum/10;
  130.             }
  131.         else 
  132.             FOD(i,m-n-1,0) 
  133.             {
  134.                 int sum = ((s[i] - '0') + c);
  135.                 x += sum%10+'0';
  136.                 c = sum/10;
  137.             }
  138.         if (c) x += c+'0';
  139.         while (x.size() > 1 and x.back() == '0') x.pop_back();
  140.         reverse(all(x));
  141.         return bignum(x);
  142.     }
  143.  
  144.     bignum operator-(const bignum &a) {
  145.         string x = "";
  146.         int m = s.size(), n = a.s.size();
  147.         int d = m-n, c = 0;
  148.         FOD(i,n-1,0)
  149.         {
  150.             int sub = ((s[i+d]-'0')-(a.s[i]-'0')-c);
  151.             if (sub < 0) 
  152.             {
  153.                 sub += 10;
  154.                 c = 1;
  155.             } 
  156.             else c = 0;
  157.             x += sub+'0';
  158.         }
  159.         FOD(i,m-n-1,0) 
  160.         {
  161.             if (s[i] == '0' and c) 
  162.             {
  163.                 x += '9';
  164.                 continue;
  165.             }
  166.             int sub = ((s[i]-'0')-c);
  167.             if (i > 0 or sub > 0) x += sub + '0';
  168.             c = 0;
  169.         }
  170.         while (x.size() > 1 and x.back() == '0') x.pop_back();
  171.         reverse(all(x));
  172.         return bignum(x);
  173.     }
  174.  
  175.     bignum operator*(const bignum &a) {
  176.         int m = s.size(), n = a.s.size();
  177.         string x(m+n, '0');
  178.         int p = 0;
  179.         FOD(i,m-1,0) 
  180.         {
  181.             int c = 0, q = 0;
  182.             FOD(j,n-1,0) 
  183.             {
  184.                 int sum = (s[i]-'0')*(a.s[j]-'0')+x[p+q]-'0'+c;
  185.                 x[p+q] = sum%10+'0';
  186.                 c = sum/10;
  187.                 ++q;
  188.             }
  189.             if (c > 0) x[p+q] += c;
  190.             ++p;
  191.         }
  192.         while (x.size() > 1 and x.back() == '0') x.pop_back();
  193.         reverse(all(x));
  194.         return bignum(x);
  195.     }
  196. };
  197.  
  198. namespace sub1 {
  199.  
  200. 	bool a[MASK(10)];
  201. 	int cnt[2];
  202.  
  203. 	bool approved()
  204. 	{
  205. 		vector<char> vec;
  206. 		for (char c : omega) vec.pb(c);
  207. 		sort(all(vec));
  208. 		vec.erase(unique(all(vec)),vec.end());
  209. 		return n <= 10 and vec[0] == 'a' and vec[1] == 'b';
  210. 	}
  211.  
  212. 	bool cmp(int x, int y)
  213. 	{
  214. 		FOR(i,0,n-1)
  215. 		{
  216. 			if ((BIT(x,i)) < (BIT(y,i))) return true;
  217. 			if ((BIT(x,i)) > (BIT(y,i))) return false;
  218. 		}
  219. 		return false;
  220. 	}
  221.  
  222. 	void solve(void)
  223. 	{
  224. 		FOR(mask,0,MASK(n)-1)
  225. 			if (c_bit(mask) == k)
  226. 			{
  227. 				if (BIT(mask,0) or BIT(mask,n-1)) continue;
  228. 				FOR(i,0,MASK(n)-1)
  229. 				{
  230. 					if (a[i]) continue;
  231. 					cnt[0] = cnt[1] = 0;
  232. 					a[i] = true;
  233. 					FOR(j,0,n-1)
  234. 					{
  235. 						bool cur = BIT(i,j);
  236. 						++cnt[cur];
  237. 						if (BIT(mask,j))
  238. 						{
  239. 							if ((cnt[0]&1) and (cnt[1]&1))
  240. 							{
  241. 								a[i] = false;
  242. 								break;
  243. 							}
  244. 						}
  245. 					}
  246. 					if ((cnt[0]&1) and (cnt[1]&1)) a[i] = false;
  247. 				}
  248. 			}
  249. 		vi v;
  250. 		FOD(i,MASK(n)-1,0)
  251. 			if (a[i]) v.pb(i);
  252. 		sort(all(v),cmp);
  253. 		stringstream geek;
  254. 		geek << t;
  255. 		int x;
  256. 		geek >> x;
  257. 		FOR(i,0,n-1) 
  258. 		{
  259. 			bool cnt = BIT(v[x-1],i);
  260. 			cout << char('a'+cnt);
  261. 		}
  262. 	}
  263.  
  264. }
  265.  
  266. namespace sub2 {
  267.  
  268. 	int dp[12][10][1100];
  269. 	vector<char> vec;
  270.  
  271. 	bool approved()
  272. 	{
  273. 		return n <= 10 and !k;
  274. 	}
  275.  
  276. 	int ok(int x)
  277. 	{
  278. 		int ans = 0;
  279. 		while (x) ans += x%2, x /= 2;
  280. 		return ans;
  281. 	}
  282.  
  283. 	void calc(int pos, int last, int state)
  284. 	{
  285. 		int &ans = dp[pos][last][state];
  286. 		if (pos > n) 
  287. 		{
  288. 			ans = (ok(state) <= 1);
  289. 			return;
  290. 		}
  291. 		if (ans != -1) return;
  292. 		ans = 0;
  293. 		FOR(j,0,vec.size()-1) 
  294. 		{
  295. 			calc(pos+1,j,state^MASK(j));
  296. 			ans += dp[pos+1][j][state^MASK(j)];
  297. 		}
  298. 	}
  299.  
  300. 	void solve(void)
  301. 	{
  302. 		fill(dp,-1);
  303. 		for (char c : omega) vec.pb(c);
  304. 		sort(all(vec));
  305. 		vec.erase(unique(all(vec)),vec.end());
  306. 		calc(1,0,0);
  307. 		stringstream geek;
  308. 		geek << t;
  309. 		int x;
  310. 		geek >> x;	
  311. 		int state = 0;
  312. 		FOR(i,1,n)
  313. 			FOR(j,0,vec.size()-1)
  314. 				if (dp[i+1][j][state^MASK(j)] < x) 
  315. 					x -= dp[i+1][j][state^MASK(j)];
  316. 				else 
  317. 				{
  318. 					cout << vec[j];
  319. 					state ^= MASK(j);
  320. 					break;
  321. 				}
  322. 	}
  323.  
  324. }
  325.  
  326. namespace sub3 {
  327.  
  328. 	bool approved()
  329. 	{
  330. 		vector<char> vec;
  331. 		for (char c : omega) vec.pb(c);
  332. 		sort(all(vec));
  333. 		vec.erase(unique(all(vec)),vec.end());
  334. 		return n <= 50 and !k and vec[0] == 'a' and vec[1] == 'b';
  335. 	}
  336.  
  337. 	void solve(void)
  338. 	{
  339. 		stringstream geek;
  340. 		geek << t;
  341. 		int x;
  342. 		geek >> x;
  343. 		if (n&1)
  344. 		{
  345. 			x--;
  346. 			FOD(i,n-1,0) 
  347. 			{
  348. 				bool cur = BIT(x,i);
  349. 				cout << char('a'+cur);
  350. 			}
  351. 			return;
  352. 		}
  353. 		int cnt = 0;
  354. 		FOD(i,n-1,1)
  355. 		{
  356. 			if (x > MASK(i-1)) 
  357. 			{
  358. 				x -= MASK(i-1);
  359. 				cout << 'b';
  360. 				++cnt;
  361. 			}
  362. 			else cout << 'a';
  363. 		}
  364. 		cout << (cnt&1?'b':'a');
  365. 	}
  366.  
  367. }
  368.  
  369. namespace sub4 {
  370.  
  371. 	bignum dp[52][6][MASK(5)];
  372. 	int len;
  373.  
  374. 	bool approved()
  375. 	{
  376. 		return n <= 50 and !k;
  377. 	}
  378.  
  379. 	int ok(int x)
  380. 	{
  381. 		int ans = 0;
  382. 		while (x) ans += x%2, x /= 2;
  383. 		return ans;
  384. 	}
  385.  
  386. 	void calc(int pos, int last, int state)
  387. 	{
  388. 		auto &ans = dp[pos][last][state];
  389. 		if (pos > n) 
  390. 		{
  391. 			ans = bignum(ok(state) <= 1?"1":"0");
  392. 			return;
  393. 		}
  394. 		if (ans != bignum("-1")) return;
  395. 		ans = bignum("0");
  396. 		FOR(j,0,len-1) 
  397. 		{
  398. 			calc(pos+1,j,state^MASK(j));
  399. 			ans = ans+dp[pos+1][j][state^MASK(j)];
  400. 		}
  401. 	}
  402.  
  403. 	void solve(void)
  404. 	{
  405. 		vector<char> vec;
  406. 		for (char c : omega) vec.pb(c);
  407. 		sort(all(vec));
  408. 		vec.erase(unique(all(vec)),vec.end());
  409. 		len = vec.size();
  410. 		FOR(i,0,n)
  411. 			FOR(j,0,len)
  412. 				FOR(mask,0,MASK(len)-1) dp[i][j][mask] = bignum("-1");
  413. 		calc(1,0,0);
  414. 		bignum x = bignum(t);	
  415. 		int state = 0;
  416. 		FOR(i,1,n)
  417. 			FOR(j,0,len-1)
  418. 				if (dp[i+1][j][state^MASK(j)] < x) 
  419. 					x = x-dp[i+1][j][state^MASK(j)];
  420. 				else 
  421. 				{
  422. 					cout << vec[j];
  423. 					state ^= MASK(j);
  424. 					break;
  425. 				}
  426. 	}	
  427.  
  428. }
  429.  
  430. namespace sub5 {
  431.  
  432. 	bignum dp[52][6][52][MASK(5)];
  433. 	int len;
  434.  
  435. 	int ok(int x)
  436. 	{
  437. 		int ans = 0;
  438. 		while (x) ans += x%2, x /= 2;
  439. 		return ans;
  440. 	}
  441.  
  442. 	void calc(int pos, int last, int level, int state)
  443. 	{
  444. 		auto &ans = dp[pos][last][level][state];
  445. 		if (pos > n) 
  446. 		{
  447. 			ans = bignum(ok(state) <= 1 and level >= k+2?"1":"0");
  448. 			return;
  449. 		}
  450. 		if (ans != bignum("-1")) return;
  451. 		ans = bignum("0");
  452. 		FOR(j,0,len-1) 
  453. 		{
  454. 			calc(pos+1,j,level+(ok(state^MASK(j)) <= 1),state^MASK(j));
  455. 			ans = ans+dp[pos+1][j][level+(ok(state^MASK(j)) <= 1)][state^MASK(j)];
  456. 		}
  457. 	}
  458.  
  459. 	void solve(void)
  460. 	{
  461. 		vector<char> vec;
  462. 		for (char c : omega) vec.pb(c);
  463. 		sort(all(vec));
  464. 		vec.erase(unique(all(vec)),vec.end());
  465. 		len = vec.size();
  466. 		FOR(i,0,n)
  467. 			FOR(j,0,len)
  468. 				FOR(cur,0,n)
  469. 					FOR(mask,0,MASK(len)-1) dp[i][j][cur][mask] = bignum("-1");
  470. 		calc(1,0,0,0);
  471. 		bignum x = bignum(t);	
  472. 		int state = 0, level = 0;
  473. 		FOR(i,1,n)
  474. 			FOR(j,0,len-1)
  475. 				if (dp[i+1][j][level+(ok(state^MASK(j)) <= 1)][state^MASK(j)] < x) 
  476. 					x = x-dp[i+1][j][level+(ok(state^MASK(j)) <= 1)][state^MASK(j)];
  477. 				else 
  478. 				{
  479. 					cout << vec[j];
  480. 					state ^= MASK(j);
  481. 					level += (ok(state) <= 1);
  482. 					break;
  483. 				}
  484. 	}	
  485.  
  486. }
  487.  
  488. signed main()
  489. {
  490.     fast;
  491.     if (fopen(name".inp","r"))
  492.     {
  493.     	freopen(name".inp","r",stdin);
  494.     	freopen(name".out","w",stdout);
  495.     }
  496.     cin >> n >> k >> omega >> t;
  497.     // if (sub1::approved()) return sub1::solve(), time(), 0;
  498.     // if (sub2::approved()) return sub2::solve(), time(), 0;
  499.     // if (sub3::approved()) return sub3::solve(), time(), 0;
  500.     // if (sub4::approved()) return sub4::solve(), time(), 0;
  501.     sub5::solve();
  502.     time();
  503.     return 0;
  504. }
  505. // ██░ ██  █    ██  ███▄    █   ▄████
  506. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  507. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  508. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  509. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  510. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  511. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  512. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  513. // ░  ░  ░   ░              ░       ░
  514.  
Success #stdin #stdout #stderr 0.02s 21116KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
-------------Time:13.309ms.
https://ideone.com/ZpiV1a
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!