Submission #349089

#	Time	Username	Problem	Language	Result	Execution time	Memory
349089		ali_tavakoli	Permutation Recovery (info1cup17_permutation)	C++17	43 / 100	4059 ms	11768 KiB

Main

//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define pb push_back
#define F first
#define S second
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
 
const int maxn = 4e4 + 5;
 
string tafrigh(string a, string b)
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	while(b.size() > 1&& b[b.size() - 1] == '0')
		b.pop_back();
	
	int B = b.size(), A = a.size();
	while(B ++ < A)
		b.pb('0');
	int now = 0;
	//cout << a.size() << " " << b.size() << '\n';
	//return a;
	for(int i = 0; i < (int)b.size(); i++)
	{
		int x = b[i] - '0' + now;
		now = 0;
		while(a[i] - '0' < x)
		{
			a[i] += 10;
			now += 10;
		}
		a[i] -= x;
		/*if(a[i] >= b[i])
			a[i] -= (b[i] - '0');
		else
		{
			a[i] += 10;
			a[i] -= (b[i] - '0');
			now += 10;
		}
		if(a[i] - '0' >= now)
		{
			a[i] -= now;
			now = 0;
		}
		else
		{
			a[i] += 10;
			a[i] -= now;
			now = 10;
		}*/
		now /= 10;
	}
	a.pb('0');
	//cout << a << " " << b << '\n';
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	reverse(a.begin(), a.end());
	
	return a;
 
}
 
string jam(string a, string b)
{
	if(a.size() < b.size())
		swap(a, b);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	while(b.size() > 1&& b[b.size() - 1] == '0')
		b.pop_back();
	int B = b.size(), A = a.size();
	while(B ++ < A)
		b.pb('0');
	
	int now = 0;
	//cout << a.size() << " " << b.size() << '\n';
	//return a;
	for(int i = 0; i < (int)b.size(); i++)
	{
		int x = a[i] - '0' + b[i] - '0' + now;
		a[i] = x % 10 + '0';
		now = x / 10;
	}
	a.pb(now + '0');
	a.pb('0');
	//cout << a << " " << b << '\n';
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	reverse(a.begin(), a.end());
	return a;
 
}
 
bool is2(string a, string b)
{
	reverse(a.begin(), a.end());
	//reverse(b.begin(), b.end());
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	/*while(b.size() > 1&& b[b.size() - 1] == '0')
		b.pop_back();*/
	int now = 1;
	for(int i = 0; i < (int)a.size(); i++)
	{
		int x = a[i] - '0';
		x *= 2;
		x += now;
		now = x / 10;
		a[i] = x % 10 + '0';
	}
	a.pb(now + '0');
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	/*while(b.size() > 1&& b[b.size() - 1] == '0')
		b.pop_back();*/
	//reverse(b.begin(), b.end());
	reverse(a.begin(), a.end());
	//cout << a << '\n';
	return (a == b);
}
 
int n, par[maxn], num[maxn], par2[maxn];
string a[maxn], last, o = "1";
bool use[maxn];
 
int getpar2(int v)
{
	return (v == par2[v] ? v : par2[v] = getpar2(par2[v]));
}
 
int getpar(int v)
{
	return (v == par[v] ? v : par[v] = getpar(par[v]));
}
 
 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	/*srand(time(0));
	int level = 1000000;
	while(level --)
	{
		int x = rand() % 1000;
		int z = x * 2 + 1;
		//int d = x - y;
		//cout << x - y << " ";
		string X, Y, o = "1", Z;
		while(x)
		{
			X.pb(x % 10 + '0');
			x /= 10;
		}
		while(z)
		{
			Z.pb(z % 10 + '0');
			z /= 10;
		}
		reverse(X.begin(), X.end());
		reverse(Z.begin(), Z.end());
		//cout << X << " " << Y << '\n';
		
		Y = X + X + o + Z - Z;
		if(!is2(X, Y))
			cout << X << " " << Y << '\n';
		//cout << is2(X, Y) << '\n';
	}
	return 0;
	string A = "15", B = "31";
	cout << A - B << '\n';
	cout << A + B << '\n';
	cout << is2(A, B) << '\n';
	cout << A << " " << B << '\n';
	return 0;*/
	//string last = a[1];
	a[0] = "0";
	cin >> n >> a[1];
	for(int i = 2; i <= n; i++)
	{
		cin >> a[i];
		//string tmp = a[i];
		//a[i] = a[i] - last;
		//last = tmp;
	}
	for(int i = 0; i < maxn; i++)
		par[i] = par2[i] = i;
	
	int mx = n;
	//string now = "";
	//int lst = 1;
	set<int> st;
	for(int i = 1; i <= n; i++)
		if(jam(jam(a[i - 1], a[i - 1]), o) == a[i])
			st.insert(i);
	//cout << st.size() << '\n';
	
	while(mx > 0&& st.size())
	{
		//int ptr = -1;
		//for(int i = 1; i <= n; i++)
		//	cout << a[i] << " ";
		//cout << '\n';
		/*for(int i = getpar(lst); i <= n; i++)
		{
			if(use[i])
				continue;
			int p = getpar(i - 1);
			//cout << i << " " << getpar(i - 1) << '\n';
			if(use[p])
				continue;
			if(jam(jam(a[p], a[p]), o) == a[i])
			{
				ptr = i;
				mi = tafrigh(a[i], a[p]);
			}
		}*/
		//cout << ptr << '\n';
		//cout << ptr << '\n';
		//if(ptr == -1|| ptr == 0)
		//	break;
		int ptr = *--st.end();
		st.erase(ptr);
		//continue;
		//cout << ptr << '\n';
		string mi;
		//cout << a[ptr] << " " << a[getpar(ptr - 1)] << " " << mi << '\n';
		mi = tafrigh(a[ptr], a[getpar(ptr - 1)]);
		num[ptr] = mx --;
		par[ptr] = getpar(ptr - 1);
		par2[ptr] = getpar2(ptr + 1);
		use[ptr] = 1;
		//lst = getpar(ptr);
		//a[ptr] = a[ptr] - a[getpar(ptr - 1)];
		//cout << a[ptr] << '\n';
		//cout << '\n';
		for(int i = getpar2(ptr); i <= n;)
		{
			//cout << i << " " << a[i] << " " << mi << '\n';
			st.erase(i);
			a[i] = tafrigh(a[i], mi);
			if(is2(a[getpar(i - 1)], a[i]))
				st.insert(i);
			//if(getpar2(i + 1) <= n&& jam(jam(a[i], a[i]), o) == a[getpar2(i + 1)])
			//	st.insert(getpar2(i + 1));
			i = getpar2(i + 1);
			//cout << i << " " << a[i] << '\n';
		}
		//cout << '\n';
		//st.erase(ptr);
		//a[ptr] = '0';
	}
	for(int i = 1; i <= n; i++)
	{
		//if(num[i] == 0)
		//	num[i] = mx --;
		cout << num[i] << " ";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6