From fdff564b14ea72719852a38e9eca7d61f2cf01af Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Tue, 9 Mar 2021 16:57:08 +0800
Subject: import(solutions): Add problem 1221.

---
 works/solutions/acwing/1221.cpp | 45 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
 create mode 100644 works/solutions/acwing/1221.cpp

diff --git a/works/solutions/acwing/1221.cpp b/works/solutions/acwing/1221.cpp
new file mode 100644
index 0000000..9ba4229
--- /dev/null
+++ b/works/solutions/acwing/1221.cpp
@@ -0,0 +1,45 @@
+#include <cmath>
+#include <iostream>
+
+const int M = 5000010;
+const int SM = std::sqrt(M / 2);
+
+int s[M];
+
+int main() {
+  int n;
+  std::cin >> n;
+
+  for (int i = 0; i <= SM; i++) {
+    const int i2 = i * i;
+    const int SMB = M - i2;
+    for (int j = i; j * j < SMB; j++) {
+      const int a = i2 + j * j;
+
+      if (s[a] == 0) {
+        s[a] = i + 1;
+      }
+    }
+  }
+
+  int sm = std::sqrt(n);
+
+  for (int a = 0; a <= sm; a++) {
+    int as = a * a;
+    int bsm = n - 3 * a * a;
+    for (int b = a; b * b <= bsm; b++) {
+      int bs = b * b + as;
+
+      int c = s[n - bs];
+
+      if (c != 0) {
+        c = c - 1;
+        std::cout << a << ' ' << b << ' ' << c << ' '
+                  << std::sqrt(n - bs - c * c);
+        return 0;
+      }
+    }
+  }
+
+  return 0;
+}
-- 
cgit v1.2.3