QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#772923#3596. New MathswcyQwQAC ✓0ms3864kbC++141.3kb2024-11-22 22:59:222024-11-22 22:59:23

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 22:59:23]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3864kb
  • [2024-11-22 22:59:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

string s;

map<string, int> ans;
int conv[30];

void dfs(string t) {
  if (t.size() == (s.size() + 1) / 2) {
    for (int i = 0; i < s.size(); i++) {
      if (s[i] - '0' != conv[i]) return;
    }
    reverse(t.begin(), t.end());
    ans[t];
    return;
  }
  for (int d = 0; d <= 9; d++) {
    if (!t.size()) {
      if (d * d % 10 == s[0] - '0') {
        conv[0] = d * d % 10;
        t += '0' + d;
        dfs(t);
        t.pop_back();
        conv[0] = 0;
      }
    }
    else {
      int ck = (conv[t.size()] + 2 * d * (t[0] - '0')) % 10;
      if (ck == s[t.size()] - '0') {
        for (int i = 0; i < t.size(); i++) (conv[t.size() + i] += 2 * d * (t[i] - '0')) %= 10;
        conv[2 * t.size()] = d * d % 10;
        t += '0' + d;
        dfs(t);
        t.pop_back();
        for (int i = 0; i < t.size(); i++) (conv[t.size() + i] -= 2 * d * (t[i] - '0')) %= 10, (conv[t.size() + i] += 10) %= 10;
        conv[2 * t.size()] = 0;
      }
    }
  }
} 

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> s;
  reverse(s.begin(), s.end());
  if (s.size() % 2 == 0) cout << -1 << '\n';
  else {
    dfs("");
    cout << (ans.size() ? (*ans.begin()).first : "-1") << '\n';
  }
  return 0;
}

详细

Test #1:

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

input:

6

output:

4

result:

ok single line: '4'

Test #2:

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

input:

149

output:

17

result:

ok single line: '17'

Test #3:

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

input:

123476544

output:

11112

result:

ok single line: '11112'

Test #4:

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

input:

15

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

255768423183

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

45665732555

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

129862724660409

output:

11450607

result:

ok single line: '11450607'

Test #8:

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

input:

423019449793954427977

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

27121

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

1062062012267214086

output:

1086309746

result:

ok single line: '1086309746'

Test #11:

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

input:

7121439534552006831

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

2331

output:

-1

result:

ok single line: '-1'

Test #13:

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

input:

664

output:

42

result:

ok single line: '42'

Test #14:

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

input:

48960202843634584

output:

270467972

result:

ok single line: '270467972'

Test #15:

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

input:

950191368742123

output:

-1

result:

ok single line: '-1'

Test #16:

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

input:

6838729832825874768072709

output:

4195767732753

result:

ok single line: '4195767732753'

Test #17:

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

input:

126412441

output:

16521

result:

ok single line: '16521'

Test #18:

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

input:

4466447004844686806

output:

2609442604

result:

ok single line: '2609442604'

Test #19:

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

input:

4

output:

2

result:

ok single line: '2'

Test #20:

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

input:

90074858599988014

output:

-1

result:

ok single line: '-1'

Test #21:

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

input:

9498578088490196330623

output:

-1

result:

ok single line: '-1'

Test #22:

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

input:

82

output:

-1

result:

ok single line: '-1'

Test #23:

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

input:

8925123681749359895

output:

-1

result:

ok single line: '-1'

Test #24:

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

input:

9008004

output:

3008

result:

ok single line: '3008'