QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#851809#5729. Carry Cam FailureWeaRD276AC ✓1ms3880kbC++201.9kb2025-01-11 01:13:442025-01-11 01:13:47

Judging History

This is the latest submission verdict.

  • [2025-01-11 01:13:47]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3880kb
  • [2025-01-11 01:13:44]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;

string sqr(const string& s)
{
	int n = sz(s);
	int len = 2 * n - 1;
	string res(len, '0');
	FOR (i, 0, n)
	{
		FOR (j, 0, n)
		{
			int d = (s[i] - '0') * (s[j] - '0') % 10;
			int pr = (res[i + j] - '0') % 10;
			res[i + j] = ((d + pr) % 10) + '0';
		}
	}
	return res;
}

string ans;

void f(string s, const int len, const string& tar)
{
	if (sz(s) == len)
	{
		//cerr << "s = " << s << '\n';
		//reverse(all(s));
		string sq = sqr(s);
		if (sq == tar)
		{
			reverse(all(s));
			if (ans.empty() || ans > s)
				ans = s;
		}
		return;
	}
	FOR (d, 0, 10)
	{
		int sm = 0;
		int n = sz(s);
		s += d + '0';
		FOR (i, 0, n + 1)
		{
			sm += (s[i] - '0') * (s[n - i] - '0');
			sm %= 10;
		}
		if (sm == tar[n] - '0')
			f(s, len, tar);
		s.pop_back();
	}
}

int solve()
{
	string num;
	if (!(cin >> num))
		return 1;
	
	int n = sz(num);
	if (!(n & 1))
	{
		cout << "-1\n";
		return 0;
	}
	
	ans = "";
	reverse(all(num));
	int len = (n + 1) / 2;
	f("", len, num);
	if (ans.empty())
		ans = "-1";
	cout << ans << '\n';
	
	return 0;
}

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int TET = 1e9;
	//cin >> TET;
	for (int i = 1; i <= TET; i++)
	{
		if (solve())
		{
			break;
		}
		#ifdef ONPC
			cerr << "_____________________________\n";
		#endif
	}
	#ifdef ONPC
		cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
	#endif
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

6

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

149

output:

17

result:

ok single line: '17'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

123476544

output:

11112

result:

ok single line: '11112'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

15

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

255768423183

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

45665732555

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

129862724660409

output:

11450607

result:

ok single line: '11450607'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

423019449793954427977

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

27121

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

1062062012267214086

output:

1086309746

result:

ok single line: '1086309746'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

7121439534552006831

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

2331

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

664

output:

42

result:

ok single line: '42'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

48960202843634584

output:

270467972

result:

ok single line: '270467972'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

950191368742123

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

6838729832825874768072709

output:

4195767732753

result:

ok single line: '4195767732753'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

126412441

output:

16521

result:

ok single line: '16521'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

4466447004844686806

output:

2609442604

result:

ok single line: '2609442604'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

90074858599988014

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

9498578088490196330623

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

82

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

8925123681749359895

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

9008004

output:

3008

result:

ok single line: '3008'