Submission #631520

#	Time	Username	Problem	Language	Result	Execution time	Memory
631520		dozer	Tavan (COCI16_tavan)	C++14	80 / 80	3 ms	2644 KiB

tavan

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define N 100005
#define modulo 1000000007
#define int long long

int val[N], arr[N], ind[N], ch[N];
vector<int> op[N];

int32_t main()
{
	fastio();

	int n, m, k, x;
	cin>>n>>m>>k>>x;

	int cntr = 0;
	for (int i = 1; i <= n; i++)
	{
		char tmp;
		cin>>tmp;
		if (tmp == '#') 
		{
			cntr++;
			ind[cntr] = i;
		}
		else arr[i] = tmp - 'a' + 1;
	}

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= k; j++)
		{
			char tmp;
			cin>>tmp;
			op[i].pb(tmp - 'a' + 1);
		}
		sort(op[i].begin(), op[i].end());
	}

	x--;
	int it = m;
	val[it] = 1;
	while(val[it] <= x)
	{
		it--;
		val[it] =  val[it + 1] * k;
	}

	while(it <= m && x > 0)
	{
		while(val[it] <= x)
		{
			x -= val[it];
			ch[it]++;
		}
		it++;
	}

	for (int i = 1; i <= m; i++)
		arr[ind[i]] = op[i][ch[i]];

	for (int i = 1; i <= n; i++)
		cout<<(char)(arr[i] + 'a' - 1);
	cout<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

• Subtask 1: 80 / 80