fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ivector = vector<int>;
  4. using imatrix = vector<ivector>;
  5.  
  6. inline istream& operator>>(istream& is, ivector& vector) {
  7.     for (auto& elem: vector)
  8.         is >> elem;
  9.     return is; }
  10.  
  11. inline ostream& operator<<(ostream& os, const ivector& vector) {
  12.     for (auto elem: vector)
  13.         os << elem << ' ';
  14.     return os; }
  15.  
  16. inline ostream& operator<<(ostream& os, const imatrix& matrix) {
  17.     for (auto vector: matrix)
  18.         os << vector << '\n';
  19.     return os; }
  20.  
  21. struct accepted_Solution {
  22.     struct imap: map<int,int> {
  23.         imap(const ivector& nums) {
  24.             auto& count = *this;
  25.             for (auto num: nums)
  26.                 ++count[num]; }
  27.         void check(imatrix& A, int x, int y) const {
  28.             const auto z = -(x+y);
  29.             const auto it = lower_bound(z);
  30.             if (it == end() or it->first > z)
  31.                 return;
  32.             if (z < y or (z == y and it->second == 1))
  33.                 return;
  34.             A.push_back({x,y,z}); }
  35.         void check_1(imatrix& A, int x) const {
  36.             for (auto it = lower_bound(x), ie = end(); it != ie; ++it) {
  37.                 const auto [y,other_count] = *it;
  38.                 if (y > x or other_count > 1)
  39.                     check(A,x,y); } }
  40.         void check_2(imatrix& A, int x) const {
  41.             for (auto it = lower_bound(x), ie = end(); it != ie; ++it)
  42.                 check(A,x,it->first); } };
  43.     imatrix threeSum(ivector& nums) {
  44.         imatrix A;
  45.         const imap g(nums);
  46.         for (auto [x,count]: g)
  47.             if (x == 0) {
  48.                 if (count > 2)
  49.                     A.emplace_back(3,0); }
  50.             else if (count == 1)
  51.                 g.check_1(A,x);
  52.             else
  53.                 g.check_2(A,x);
  54.         return A; } };
  55.  
  56. class other_Solution {
  57. public:
  58.     imatrix threeSum(ivector N) {
  59.         sort(N.begin(), N.end());
  60.         int n = N.size();
  61.         imatrix A;
  62.         for (int i = 0; i < n-2; i++) {
  63.             if (i > 0 and N[i] == N[i-1])
  64.                 continue;
  65.             int l = i+1, r = n-1;
  66.             while (l < r) {
  67.                 if (N[i] + N[l] + N[r] > 0)
  68.                     r--;
  69.                 else if(N[i] + N[l] + N[r] < 0)
  70.                     l++;
  71.                 else {
  72.                     A.push_back({N[i], N[l], N[r]});
  73.                     int x = N[l];
  74.                     int y = N[r];
  75.                     while (x == N[l] and l < n)
  76.                         l++;
  77.                     while (y == N[r] and r >= 0)
  78.                         r--; } } }
  79.         return A; } };
  80.  
  81. int main() {
  82.     const auto do_hack = true;
  83.     random_device device;
  84.     mt19937_64 random(device());
  85.     int N;
  86.     ivector nums;
  87.     if (cin >> N, nums.resize(N), do_hack) {
  88.         int max_value, generated_test_cases;
  89.         cin >> max_value>> generated_test_cases;
  90.         uniform_int_distribution<int> uniform(-max_value,max_value);
  91.         while (generated_test_cases--) {
  92.             for (auto& num: nums)
  93.                 num = uniform(random);
  94.             auto output = other_Solution().threeSum(nums);
  95.             auto expected = accepted_Solution().threeSum(nums);
  96.             if (output != expected) {
  97.                 cout << "Input:" << endl << nums << endl;
  98.                 cout << "Output:" << endl << output;
  99.                 cout << "Expected:" << endl << expected; } }
  100.         cout << "passed"; }
  101.     else
  102.         cin >> nums, cout << accepted_Solution().threeSum(nums);
  103.     return 0; }
  104.  
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
10 10 1000
stdout
copy 
passed
https://ideone.com/0r27lJ
3Sum
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!