QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#552954#7704. Plus Minus Four Squaresstig#AC ✓1ms3776kbC++202.4kb2024-09-08 04:21:482024-09-08 04:21:49

Judging History

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

  • [2024-09-08 04:21:49]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3776kb
  • [2024-09-08 04:21:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

typedef int uci;
#define int long long
#define ld long double
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

uci main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    int mx = sqrt(n);
    int ans{};
    for (int a = 0; a <= mx; a++) {
        int a2 = a * a, aneg = (a < 0 ? -1 : 1);
        for (int b = -abs(a); b <= abs(a); b++) {
            int b2 = b * b, bneg = (b < 0 ? -1 : 1);
            if (abs(a) == abs(b) && a != b) continue;

            for (int c = -abs(b); c <= abs(b); c++) {
                int c2 = c * c, cneg = (c < 0 ? -1 : 1);
                if (abs(c) == abs(b) && b != c) continue;

                int d2 = n - (a2 * aneg + b2 * bneg + c2 * cneg);
                int dneg = (d2 < 0 ? -1 : 1);
                // dbg(a, b, c, d2);
                // 1. d2 has to be perfect square
                // 2. if abs(d) == abs(c), sign has to be the same

                int d = sqrt(abs(d2));
                if (d * d != abs(d2)) continue;
                if (d > abs(c)) continue;
                if (abs(d2) == c2 && (d2 < 0 != c < 0)) continue;

                int test = a2 * aneg + b2 * bneg + c2 * cneg + d * d * dneg;
                if (test != n || b2 > a2 || c2 > b2 || d * d > c2 ||
                    (a2 == b2 && aneg != bneg) || (b2 == c2 && bneg != cneg) || (c2 == d * d && cneg != dneg)) {
                    cout << "bad" << '\n';
                    dbg(a, b, c, d * dneg);
                }

                ans++;
            }
        }
    }

    cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

64

output:

12

result:

ok single line: '12'

Test #2:

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

input:

65

output:

10

result:

ok single line: '10'

Test #3:

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

input:

2023

output:

245

result:

ok single line: '245'

Test #4:

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

input:

0

output:

1

result:

ok single line: '1'

Test #5:

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

input:

5000

output:

951

result:

ok single line: '951'

Test #6:

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

input:

1024

output:

182

result:

ok single line: '182'

Test #7:

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

input:

2048

output:

355

result:

ok single line: '355'

Test #8:

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

input:

4096

output:

708

result:

ok single line: '708'

Test #9:

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

input:

1

output:

1

result:

ok single line: '1'

Test #10:

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

input:

2

output:

1

result:

ok single line: '1'

Test #11:

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

input:

4

output:

2

result:

ok single line: '2'

Test #12:

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

input:

3

output:

1

result:

ok single line: '1'

Test #13:

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

input:

1111

output:

131

result:

ok single line: '131'