fork(1) download
copy 
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<algorithm>
  4. #include<stack>
  5. #include<queue>
  6. #include<string>
  7. #include<string.h>
  8. #include<cmath>
  9. #include<vector>
  10. #include<map>
  11. #include<unordered_map>
  12. #include<set>
  13. #include<unordered_set>
  14. #include<cstdio>
  15. #include<bitset>
  16. #include<chrono>
  17. #include<random>
  18. #include<ext/rope>
  19. /* ordered_set
  20. #include<ext/pb_ds/assoc_container.hpp>
  21. #include<ext/pb_ds/tree_policy.hpp>
  22. using namespace __gnu_pbds;
  23. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  24. */
  25. #define int long long
  26. #define pb push_back
  27. #define fi first
  28. #define se second
  29. using namespace std;
  30. using ll = long long;
  31. using ld = long double;
  32. using ull = unsigned long long;
  33. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  34. const int maxN = 40 + 5;
  35. const int mod = 1e9 + 7;
  36. const ll oo = 1e18;
  37. int n;
  38. int xg, yg;
  39. ll res[maxN];
  40. vector<pair<int, int>> vc1[maxN], vc2[maxN];
  41. int n1, n2;
  42. struct TPoint
  43. {
  44.     int x, y;
  45. } a[maxN], a1[maxN], a2[maxN];
  46. inline void FastInput()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50. }
  51. void ReadInput()
  52. {
  53.     cin >> n >> xg >> yg;
  54.     for(int i=1; i<=n; i++) cin >> a[i].x >> a[i].y;
  55. }
  56. int pos[maxN];
  57. void Attempt1(int t)
  58. {
  59.     if(t == n1 + 1)
  60.     {
  61.         ll x = 0, y = 0;
  62.         int cnt = 0;
  63.         for(int i=1; i<=n1; i++)
  64.         {
  65.             if(pos[i])
  66.             {
  67.                 cnt++;
  68.                 x += a1[i].x;
  69.                 y += a1[i].y;
  70.             }
  71.         }
  72.         vc1[cnt].pb({x, y});
  73.         return;
  74.     }
  75.     for(pos[t]=0; pos[t]<=1; pos[t]++) Attempt1(t + 1);
  76. }
  77. void Attempt2(int t)
  78. {
  79.     if(t == n2 + 1)
  80.     {
  81.         int cnt = 0;
  82.         ll x = 0, y = 0;
  83.         for(int i=1; i<=n2; i++)
  84.         {
  85.             if(pos[i])
  86.             {
  87.                 cnt++;
  88.                 x += a2[i].x;
  89.                 y += a2[i].y;
  90.             }
  91.         }
  92.         vc2[cnt].pb({x, y});
  93.         return;
  94.     }
  95.     for(pos[t]=0; pos[t]<=1; pos[t]++) Attempt2(t + 1);
  96. }
  97. void Solve()
  98. {
  99.     n1 = n / 2;
  100.     n2 = n - n1;
  101.     for(int i=1; i<=n1; i++) a1[i] = a[i];
  102.     for(int i=1; i<=n2; i++) a2[i] = a[i + n1];
  103.     Attempt1(1);
  104.     Attempt2(1);
  105.     for(int i=1; i<=n1; i++)
  106.         sort(vc1[i].begin(), vc1[i].end());
  107.     for(int i=1; i<=n2; i++)
  108.         sort(vc2[i].begin(), vc2[i].end(), greater<pair<int, int>>());
  109.     //for(pair<int, int> v : vc2[4]) cout << v.fi << " " << v.se << '\n';return;
  110.     for(int i=0; i<=n1; i++)
  111.     {
  112.         for(int k=0; k<=n2; k++)
  113.         {
  114.             int p = 0;
  115.             int mul1 = 1;
  116.             for(int j=0; j<vc1[i].size(); j++)
  117.             {
  118.                 while(j + 1 < vc1[i].size() && vc1[i][j].fi == vc1[i][j + 1].fi && vc1[i][j].se == vc1[i][j + 1].se)
  119.                 {
  120.                     mul1++;
  121.                     j++;
  122.                 }
  123.                 int x = xg - vc1[i][j].fi, y = yg - vc1[i][j].se;
  124.                 while(p < vc2[k].size() && vc2[k][p].fi > x) p++;
  125.                 while(p < vc2[k].size() && vc2[k][p].se > y && vc2[k][p].fi == x) p++;
  126.                 int mul = 0;
  127.                 while(p < vc2[k].size() && vc2[k][p].fi == x && vc2[k][p].se == y)
  128.                 {
  129.                     mul++;
  130.                     p++;
  131.                 }
  132.                 res[i + k] += mul * mul1;
  133.                 mul1 = 1;
  134.             }
  135.         }
  136.     }
  137.     for(int i=1; i<=n; i++) cout << res[i] << '\n';
  138. }
  139. int32_t main()
  140. {
  141.     //freopen("x.inp", "r", stdin);
  142.     FastInput();
  143.     ReadInput();
  144.     Solve();
  145. }
  146.  
Success #stdin #stdout 0s 5432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c2Qwta
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!