oj.uz

Submission #349079

# Submission time Handle Problem Language Result Execution time Memory
349079 2021-01-16T15:10:47 Z ali_tavakoli Permutation Recovery (info1cup17_permutation) C++14
43 / 100
 4000 ms 17140 KB 
//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("Ofast")

const int maxn = 7e4 + 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];
string a[maxn], last, o = "1";
bool use[maxn];

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] = i;
	}
	
	int mx = n;
	//string now = "";
	while(mx > 0)
	{
		int ptr = -1;
		//for(int i = 1; i <= n; i++)
		//	cout << a[i] << " ";
		//cout << '\n';
		string mi;
		for(int i = 1; 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]);
			}
			/*else
				cout << a[p] << " " << a[i] << '\n';*/
		}
		//cout << ptr << '\n';
		//cout << ptr << '\n';
		//if(ptr == -1|| ptr == 0)
		//	break;
		num[ptr] = mx --;
		par[ptr] = getpar(ptr - 1);
		use[ptr] = 1;
		//a[ptr] = a[ptr] - a[getpar(ptr - 1)];
		//cout << a[ptr] << '\n';
		//cout << '\n';
		for(int i = ptr; i <= n; i++)
		{
			if(!use[i])
				a[i] = tafrigh(a[i], mi);
			//cout << i << " " << a[i] << '\n';
		}
		//a[ptr] = '0';
	}
	for(int i = 1; i <= n; i++)
	{
		//if(num[i] == 0)
		//	num[i] = mx --;
		cout << num[i] << " ";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct
3 Correct 400 ms 3052 KB Output is correct
4 Correct 266 ms 2924 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct
3 Correct 400 ms 3052 KB Output is correct
4 Correct 266 ms 2924 KB Output is correct
5 Execution timed out 4056 ms 17140 KB Time limit exceeded

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct
3 Correct 400 ms 3052 KB Output is correct
4 Correct 266 ms 2924 KB Output is correct
5 Execution timed out 4056 ms 17140 KB Time limit exceeded

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct
3 Correct 400 ms 3052 KB Output is correct
4 Correct 266 ms 2924 KB Output is correct
5 Execution timed out 4056 ms 17140 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct
3 Correct 400 ms 3052 KB Output is correct
4 Correct 266 ms 2924 KB Output is correct
5 Execution timed out 4056 ms 17140 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 28 ms 2796 KB Output is correct
3 Correct 400 ms 3052 KB Output is correct
4 Correct 266 ms 2924 KB Output is correct
5 Execution timed out 4056 ms 17140 KB Time limit exceeded