Submission #348996

#	Time	Username	Problem	Language	Result	Execution time	Memory
348996		ali_tavakoli	Permutation Recovery (info1cup17_permutation)	C++14	0 / 100	2 ms	2796 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("Ofast")

const int maxn = 7e4 + 5;

string operator-(string a, string b)
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	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 < b.size(); i++)
	{
		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;
	}
	//cout << a << " " << b << '\n';
	while(a.size() > 1&& a[a.size() - 1] == '0')
		a.pop_back();
	reverse(a.begin(), a.end());
	return a;

}

string operator+(string a, string b)
{
	if(a.size() < b.size())
		swap(a, b);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	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 < b.size(); i++)
	{
		int x = a[i] - '0' + b[i] - '0' + now;
		a[i] = x % 10 + '0';
		now = x / 10;
	}
	while(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());
	int now = 1;
	for(int i = 0; i < 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();
	reverse(a.begin(), a.end());
	//cout << a << '\n';
	return (a == b);
}

int n, par[maxn], num[maxn];
string a[maxn], last;
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);
	/*string A = "1", B = "1";
	cout << A - B << '\n';
	//cout << is2(A, B) << '\n';
	return 0;*/
	cin >> n >> a[1];
	//string last = 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';
		for(int i = 2; i <= n; i++)
		{
			if(use[i])
				continue;
			int p = getpar(i - 1);
			//cout << i << " " << getpar(i - 1) << '\n';
			if(!p|| use[p])
				continue;
			if(is2(a[p], a[i]))
				ptr = i;
			/*else
				cout << a[p] << " " << a[i] << '\n';*/
		}
		//cout << ptr << '\n';
		//cout << ptr << '\n';
		if(ptr == -1|| ptr == 0)
			break;
		num[ptr] = mx --;
		par[ptr] = ptr - 1;
		use[ptr] = 1;
		a[ptr] = a[ptr] - a[getpar(ptr - 1)];
		//cout << a[ptr] << '\n';
		//cout << '\n';
		for(int i = ptr + 1; i <= n; i++)
		{
			//if(!use[i])
				a[i] = a[i] - a[ptr];
			//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] << " ";
	}
}

Compilation message (stderr)

permutation.cpp: In function 'std::string operator-(std::string, std::string)':
permutation.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0; i < b.size(); i++)
      |                 ~~^~~~~~~~~~
permutation.cpp: In function 'std::string operator+(std::string, std::string)':
permutation.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i = 0; i < b.size(); i++)
      |                 ~~^~~~~~~~~~
permutation.cpp: In function 'bool is2(std::string, std::string&)':
permutation.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i = 0; i < a.size(); i++)
      |                 ~~^~~~~~~~~~

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