QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876212#7704. Plus Minus Four SquaresWeaRD276#WA 61ms3712kbC++203.0kb2025-01-30 18:38:202025-01-30 18:38:20

Judging History

This is the latest submission verdict.

  • [2025-01-30 18:38:20]
  • Judged
  • Verdict: WA
  • Time: 61ms
  • Memory: 3712kb
  • [2025-01-30 18:38:20]
  • Submitted

answer

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

#include  <ext/pb_ds/assoc_container.hpp>
#include  <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#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;


int solve()
{
	int n;
	if (!(cin >> n))
		return 1;
	
	int ans = 0;
	int sq = sqrt(n) + 1;
	//vector<vector<int>> ans;
	for (int a = 1; a * a <= n; a++)
	{
		for (int b = 0; b <= sq && b <= a; b++)
		{
			for (int c = 0; c <= sq && c <= b; c++)
			{
				for (int d = 0; d <= sq && d <= c; d++)
				{
					int aa = a * a;
					int bb = b * b;
					int cc = c * c;
					int dd = d * d;
					vector<int> ar{aa, bb, cc, dd};
					set<int> ss(all(ar));
					ss.erase(0);
					vector<int> arr(all(ss));
					//while (arr[0] == 0)
						//arr.erase(arr.begin());
					
					map<int, int> cnt;
					cnt[aa]++;
					cnt[bb]++;
					cnt[cc]++;
					cnt[dd]++;
					sort(rall(arr));
					//if (arr[0] > n)
						//continue;
					FOR (mask, 0, (1 << (sz(arr) - 1)))
					{
						int val = arr[0] * cnt[arr[0]];
						//vector<int> cur;
						//FOR (ccc, 0, cnt[arr[0]])
							//cur.pb(arr[0]);
						FOR (i, 0, sz(arr) - 1)
						{
							if (mask & 1 << i)
							{
								val += arr[i + 1] * cnt[arr[i + 1]];
								//assert(cnt[arr[i]] != 0);
								//FOR (ccc, 0, cnt[arr[i + 1]])
									//cur.pb(arr[i + 1]);
							}
								
							else
							{
								val -= arr[i + 1] * cnt[arr[i + 1]];
								//assert(cnt[arr[i]] != 0);
								//FOR (ccc, 0, cnt[arr[i + 1]])
									//cur.pb(-arr[i + 1]);
							}
								
						}
						//while (sz(cur) < 4)
							//cur.pb(0);
						//sort(all(cur), [](int lef, int rig)
						//{
							//return abs(lef) > abs(rig);
						//});
						
						//assert(sz(cur) == 4);
						//sort(all(cur));
						if (val == n && arr[0] <= n && arr[0] > 0)
						{
							//ans.pb(cur);
							ans++;
						}
					}
				}
			}
		}
	}
	//sort(all(ans));
	//ans.erase(unique(all(ans)), ans.end());
	
	//for (auto vv: ans)
		//cerr << vv[0] << ' ' << vv[1] << ' ' << vv[2] << ' ' << vv[3] << '\n';
		
	//cout << sz(ans) << '\n';
	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;
}

详细

Test #1:

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

input:

64

output:

12

result:

ok single line: '12'

Test #2:

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

input:

65

output:

10

result:

ok single line: '10'

Test #3:

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

input:

2023

output:

245

result:

ok single line: '245'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3584kb

input:

0

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'